题目大意：一个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$
统计答案算一下总路程加上等红灯的额外时间就行了
权值可能很大需要动态开点
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define NN 101000 5 #define ll long long 6 using namespace std; 7 8 9 int n,m,g,r,root; 10 int d[NN]; 11 ll dis[NN],f[NN]; 12 struct Seg{ 13 int tag[NN*50],val[NN*50],ls[NN*50],rs[NN*50],tot; 14 void pushdown(int rt){ 15 if(!tag[rt]) return; 16 if(!ls[rt]) ls[rt]=++tot; 17 if(!rs[rt]) rs[rt]=++tot; 18 val[ls[rt]]=val[rs[rt]]=tag[rt]; 19 tag[ls[rt]]=tag[rs[rt]]=tag[rt]; 20 tag[rt]=0; 21 } 22 void update(int L,int R,int l,int r,int &rt,int w) 23 { 24 if(!rt) rt=++tot; 25 if(L<=l&&r<=R){tag[rt]=w,val[rt]=w;return;} 26 int mid=(l+r)>>1;pushdown(rt); 27 if(L<=mid) update(L,R,l,mid,ls[rt],w); 28 if(R>mid) update(L,R,mid+1,r,rs[rt],w); 29 //pushup(rt); 30 } 31 int query(int x,int l,int r,int rt) 32 { 33 if(!rt) return 0; 34 if(l==r) return val[rt]; 35 int mid=(l+r)>>1;pushdown(rt); 36 if(x<=mid) return query(x,l,mid,ls[rt]); 37 else return query(x,mid+1,r,rs[rt]); 38 //pushup(rt); 39 } 40 }s; 41 42 int main() 43 { 44 scanf("%d%d%d",&n,&g,&r); 45 const int ma=g+r; 46 ll tot=0; 47 for(int i=1;i<=n+1;i++){ 48 scanf("%d",&d[i]); 49 tot+=d[i];d[i]%=ma; 50 dis[i]=dis[i-1]+d[i]; 51 } 52 ll L,R,w;int x,y; 53 root=1,s.tot=1; 54 for(int i=n;i>=1;i--) 55 { 56 L=((g-dis[i])%ma+ma)%ma; 57 R=((g+r-1-dis[i])%ma+ma)%ma; 58 w=((-dis[i])%ma+ma)%ma; 59 x=s.query(w,0,ma-1,root); 60 f[i]=f[x]+(x?ma-(dis[x]-dis[i])%ma:0); 61 if(L<=R){ 62 s.update(L,R,0,ma-1,root,i); 63 }else{ 64 s.update(0,R,0,ma-1,root,i); 65 s.update(L,ma-1,0,ma-1,root,i); 66 } 67 } 68 int Q; 69 scanf("%d",&Q); 70 for(int q=1;q<=Q;q++) 71 { 72 scanf("%d",&x); 73 y=s.query(x%ma,0,ma-1,root); 74 ll ret; 75 if(!y) ret=x+tot; 76 else ret=tot+f[y]+x+(ma-(x+dis[y])%ma); 77 printf("%lld ",ret); 78 } 79 return 0; 80 } 81