显然所有询问都要经过至少$\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;
}

  

最新文章

  1. (转) Qt 出现“undefined reference to `vtable for”原因总结
  2. Java基础知识点4:继承
  3. jquery实现更多内容效果
  4. J2EE基础之Servlet
  5. Linux下定时执行任务的几种方式
  6. dede使用方法----调用导航
  7. JDK 伪异步编程(线程池)
  8. c++代码美化
  9. java ConcurrentModificationException探究
  10. replace和replaceAll的区别
  11. xml装php数组
  12. 在Android应用中实现Google搜索的例子
  13. Mqtt协议IOS移植完1
  14. LeetCode219:Contains Duplicate II
  15. 将逗号分隔 的字符串转化成List
  16. attr和prop的区别以及在企业开发中应该如何抉择
  17. springboot2.0 springcloud 断路器仪表盘支持
  18. Liang-Barsky直线段裁剪算法
  19. Swift DispatchQueue
  20. TextView的实现原理介绍

热门文章

  1. B-树(B树)详解
  2. SSH框架之hibernate《三》
  3. Shpinx在PHPCMS里的使用及配置
  4. django中的一对一、一对多、多对多及ForeignKey()
  5. Python3:关于列表的操作(合并、拼接,嵌套排序&#183;&#183;)
  6. 引用变量&amp;和指针*的区别
  7. django的一些常用指令
  8. 简易解说拉格朗日对偶(Lagrange duality)
  9. centos 6 部署Nodejs
  10. python中requests的用法