[题解] CF187D BRT Contract

· · 题解

不同时刻从家出发一旦在一个位置等了红灯之后花费的时间就固定不变了 , f_i 表示从 i 位置开始等完红灯 (可以理解为时刻为 0 ) 走到终点花费的时间 , 然后倒着计算。

如何找到第一个需要等红灯的位置呢 , 如果从开始到第 i 个位置的距离模 (g+r) 余数为 p , 出发时间为 t , 如果满足 g \le (t+p) \% (g+r) 就代表需要等这个红灯 , 可以发现 t 的区间有两种情况。

p\le g : t\in[g-p,r+g-1-p] g \lt p : t\in[0,r+g-1-p]\cup[m-p+g,m-1]

维护一个线段树 , 支持区间set单点查询。

如何计算每一个 f_i 呢 , 如果倒着往前考虑到 i 时假定之前的没有经过红灯顺利过来的 , 在家等 x 秒 , 使从家到第 i 个位置刚好亮起绿灯 , 这样等价于时刻 0 ,最后花费时间减去从家到 i 的时间和等的 x 秒就是从 i 位置开始走到终点花费的时间。

对于每一个询问 , 找出第一个遇到的红灯 i , 从家到 i 的时间加等红灯的时间加 f_i 就是最终的答案。

因为值域比较大 , 要写动态开点线段树 , 注意数组开大一些。

Code

#include <cstdio>
#include <algorithm>
#include <vector>

#define int long long
#define Lid (ch[id][0])
#define Rid (ch[id][1])

using namespace std;

int read(){int qrx=0,qry=1;char qrc=getchar();
while(qrc<'0'||qrc>'9'){if(qrc=='-'){qry=-1,qrc=getchar();}else qrc=getchar();}
while(qrc>='0'&&qrc<='9')qrx=qrx*10+qrc-48,qrc=getchar();return qrx*qry;}

const int N=2e6+7,Mod=998244353,INF=1e12+7;
int n,m,G,R,d[N],X[N],f[N],Q,rt=1;
signed ch[N*8][2],tot=1,val[N*8];

void pushdown(int id,int len){
    if(val[id]&&len>1){
        if(!Lid)Lid=++tot;
        if(!Rid)Rid=++tot;
        val[Lid]=val[Rid]=val[id],val[id]=0;
    }
    return;
}

void update(int L,int R,int id,int l,int r,int x){
    pushdown(id,R-L+1);
    if(l<=L&&r>=R)val[id]=x,pushdown(id,R-L+1);
    else{
        int M=(L+R)>>1;
        if(l<=M)update(L,M,Lid,l,r,x);
        if(r>M)update(M+1,R,Rid,l,r,x);
    }
    return;
}

int query(int L,int R,int id,int x){
    pushdown(id,R-L+1);
    if(L==R)return val[id];
    int M=(L+R)>>1;
    if(x<=M)return query(L,M,Lid,x);
    else return query(M+1,R,Rid,x);
}

int Query(int t){
    int p=query(0,m-1,rt,t%m);
    int ans=t+X[p]+f[p];
    if(p<=n)ans+=m-(X[p]+t)%m;
    return ans;
}

signed main(){
    n=read(),G=read(),R=read(),m=G+R;
    for(int i=1;i<=n+1;i++)d[i]=read(),X[i]=X[i-1]+d[i];
    update(0,m-1,rt,0,m-1,n+1);
    for(int i=n,p=0;i>=1;i--){
        p=m-X[i]%m,f[i]=Query(p)-X[i]-p,p=X[i]%m;
        if(p<=G)update(0,m-1,rt,G-p,m-1-p,i);
        else update(0,m-1,rt,0,m-1-p,i),update(0,m-1,rt,m-p+G,m-1,i);
    }
    Q=read();
    for(int i=1;i<=Q;i++)printf("%lld\n",Query(read()));
    return 0;
}