注意到一旦在某个路口被红灯逼停，剩下要走的时间是固定的。容易想到预处理出在每个路口被逼停后到达终点的最短时间，这样对于每个询问求出其最早在哪个路口停下就可以了。对于预处理，从下一个要停的路口倒推即可。问题只剩下如何求出下一个要停的路口，这相当于求满足di,j%(g+r)>=g的最小j，对d做一个前缀和，那么显然满足条件的是一个值域区间，线段树维护值域区间的路口最小编号即可。对于询问要处理的也与此类似。注意家里没有红灯。（？）
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 50010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,g,r,a[N],root,cnt; ll d[N],s[N]; struct data{int l,r,x; }tree[N<<5]; void ins(int &k,int l,int r,int p,int i) { if (!k) k=++cnt,tree[k].x=n+1; tree[k].x=min(tree[k].x,i); if (l==r) return; int mid=l+r>>1; if (p<=mid) ins(tree[k].l,l,mid,p,i); else ins(tree[k].r,mid+1,r,p,i); } int query(int k,int l,int r,int x,int y) { if (!k) return n+1; if (l==x&&r==y) return tree[k].x; int mid=l+r>>1; if (y<=mid) return query(tree[k].l,l,mid,x,y); else if (x>mid) return query(tree[k].r,mid+1,r,x,y); else return min(query(tree[k].l,l,mid,x,mid),query(tree[k].r,mid+1,r,mid+1,y)); } int getnxt(ll x) { x%=g+r;if (x<0) x+=g+r; if (x<=g) return query(root,0,g+r-1,g-x,g+r-1-x); else return min(query(root,0,g+r-1,0,g+r-1-x),query(root,0,g+r-1,g+r-(x-g),g+r-1)); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj5254.in","r",stdin); freopen("bzoj5254.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),g=read(),r=read(); for (int i=0;i<=n;i++) s[i+1]=s[i]+(a[i]=read()); for (int i=n;i>=0;i--) { int nxt=getnxt(-s[i]); if (nxt==n+1) d[i]=s[n+1]-s[i]; else d[i]=d[nxt]+((s[nxt]-s[i])/(g+r)+1)*(g+r); if (i) ins(root,0,g+r-1,s[i]%(g+r),i); } m=read(); while (m--) { int x=read(); int nxt=getnxt(x); if (nxt==n+1) printf(LL,x+s[n+1]); else printf(LL,d[nxt]+((s[nxt]+x)/(g+r)+1)*(g+r)); } return 0; }