题目大意：一个wly从家走到学校要经过n个红绿灯，绿灯持续时间是$g$，红灯是$r$，所有红绿灯同时变红变绿，交通规则和现实中一样，不能抢红灯，两个红绿灯之间道路的长度是$di$，一共$Q$个询问，求他在$k$时刻出发到达学校的时间$(Q<=5*10^4)$
终于过了..jdr是真的duliu
搞了半个多下午才看懂题解
首先总路程一定大于等于$\sum d_{i}$，所以求出等红灯的总时间就行了
红绿灯的周期是$(g+r)$，所以 超过$g+r$的道路 或者 询问的时刻$k$ ，直接取模$(g+r)$即可
定义$f[i]$表示第一次在第i个位置停下(被红灯卡住)，然后等变绿以后，再走到终点的路程中，等红灯的总时间
如果我们求出了$f[i]$，那么对于每个询问，只需要找出在时刻$k$出发，第一个停下的位置就行了
如果在第$i$个位置停下，设下一个停下的位置是$j$，显然$j$是唯一的
维护一个权值线段树，值域是$[0,g+r)$，表示在x时刻出发，第一次停下的位置是$a_{x}$，由于是找出第一次停下的位置，所以倒序枚举红绿灯
如果$x$时刻出发能够在位置i停下，可得$g<=(x+dis[i])<=g+r-1$，即到达i之后恰好是红灯
然后把在线段树内把$x$的可行区间全都修改成$i$
而$f[i]$可以通过在线段树里找$-dis[i]$，得到$i$下一个停下的位置$j$
统计答案算一下总路程加上等红灯的额外时间就行了
权值可能很大需要动态开点
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NN 101000
#define ll long long
using namespace std; int n,m,g,r,root;
int d[NN];
ll dis[NN],f[NN];
struct Seg{
int tag[NN*],val[NN*],ls[NN*],rs[NN*],tot;
void pushdown(int rt){
if(!tag[rt]) return;
if(!ls[rt]) ls[rt]=++tot;
if(!rs[rt]) rs[rt]=++tot;
val[ls[rt]]=val[rs[rt]]=tag[rt];
tag[ls[rt]]=tag[rs[rt]]=tag[rt];
tag[rt]=;
}
void update(int L,int R,int l,int r,int &rt,int w)
{
if(!rt) rt=++tot;
if(L<=l&&r<=R){tag[rt]=w,val[rt]=w;return;}
int mid=(l+r)>>;pushdown(rt);
if(L<=mid) update(L,R,l,mid,ls[rt],w);
if(R>mid) update(L,R,mid+,r,rs[rt],w);
//pushup(rt);
}
int query(int x,int l,int r,int rt)
{
if(!rt) return ;
if(l==r) return val[rt];
int mid=(l+r)>>;pushdown(rt);
if(x<=mid) return query(x,l,mid,ls[rt]);
else return query(x,mid+,r,rs[rt]);
//pushup(rt);
}
}s; int main()
{
scanf("%d%d%d",&n,&g,&r);
const int ma=g+r;
ll tot=;
for(int i=;i<=n+;i++){
scanf("%d",&d[i]);
tot+=d[i];d[i]%=ma;
dis[i]=dis[i-]+d[i];
}
ll L,R,w;int x,y;
root=,s.tot=;
for(int i=n;i>=;i--)
{
L=((g-dis[i])%ma+ma)%ma;
R=((g+r--dis[i])%ma+ma)%ma;
w=((-dis[i])%ma+ma)%ma;
x=s.query(w,,ma-,root);
f[i]=f[x]+(x?ma-(dis[x]-dis[i])%ma:);
if(L<=R){
s.update(L,R,,ma-,root,i);
}else{
s.update(,R,,ma-,root,i);
s.update(L,ma-,,ma-,root,i);
}
}
int Q;
scanf("%d",&Q);
for(int q=;q<=Q;q++)
{
scanf("%d",&x);
y=s.query(x%ma,,ma-,root);
ll ret;
if(!y) ret=x+tot;
else ret=tot+f[y]+x+(ma-(x+dis[y])%ma);
printf("%lld\n",ret);
}
return ;
}