BZOJ5254 : [Fjwc2018]红绿灯

显然所有询问都要经过至少$\sum d$，只需要考虑除了$\sum d$之外的等待红灯的时间。

将所有询问的时间模$g+r$，并按时间用set维护。

那么对于每个红灯，在set中可以找出$1$到$2$个区间，将里面所有的询问暴力取出，添加一个新点作为等到绿灯后的询问放入。

那么询问与新点之间构成了一棵树结构，每个询问实际的答案为它到根路径上所有点的答案之和。

时间复杂度$O(n\log n)$。

#include<cstdio>

#include<algorithm>

#include<set>

using namespace std;

typedef long long ll;

typedef pair<ll,int>P;

const int N=150010;

int n,m,i,f[N],q[N],cnt,tot;ll A,B,per,d[N],x,w[N],sum;bool v[N];set<P>T;

inline void read(ll&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

ll dfs(int x){

  if(v[x])return w[x];

  return v[x]=1,w[x]+=dfs(f[x]);

}

inline void solve(ll L,ll R,ll K){

  cnt=0;

  while(1){

    set<P>::iterator it=T.lower_bound(P(L,0));

    if(it==T.end())break;

    if(it->first>R)break;

    q[cnt++]=it->second;

    w[it->second]+=K-it->first;

    T.erase(it);

  }

  if(!cnt)return;

  tot++;

  for(int i=0;i<cnt;i++)f[q[i]]=tot;

  T.insert(P(K%per,tot));

}

inline void fix(ll L){

  L=(per-L+A)%per;

  ll R=L+B-1,K=R+1;

  solve(L,min(R,per-1),K);

  if(R>=per)solve(0,R%per,K-per);

}

int main(){

  scanf("%d%lld%lld",&n,&A,&B);

  per=A+B;

  for(i=0;i<=n;i++)read(d[i]);

  scanf("%d",&m);

  for(i=1;i<=m;i++)read(w[i]),T.insert(P(w[i]%per,i));

  for(tot=m,i=0;i<=n;i++){

    sum+=d[i];

    if(i<n)fix(sum%per);

  }

  for(i=1;i<=m;i++)printf("%lld\n",dfs(i)+sum);

  return 0;

}