【21 ZR联赛集训 day10】跑得比谁都快

\(O(nq)\) 做法显然，不讲。

如果我们把所有红绿灯的位置 \(mod (g+r)\)，放到数据结构里，就可以 \(O(\log n)\) 的时间内找到第一个红灯的位置。

然后我们预处理每个红绿灯红灯结束的时刻开始，走到终点要用的时间 \(f_i\)，DP 倒序求解。

对于每个询问，我们找到第一个红灯的位置，答案就是直线走到这个红绿灯用时 + 等完红灯用时 +\(f_i\)。

Code

以下是用 map 维护的一个方法。map 里的元素按 \(<第一关键字，第二关键字>\) 的顺序排序。

#include<bits/stdc++.h>
#define pf printf
#define sf scanf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define isdigit(x) (x>='0'&&x<='9')
#define int ll
using namespace std;
typedef long long ll;
const int N=2e5+7,mod=2147483647;
template <typename T>
void read(T &sum){
	sum=0;
	T fl=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) (ch=='-')&&(fl=-1);
	for(;isdigit(ch);ch=getchar()) sum=(sum<<3)+(sum<<1)+ch-'0';
	sum=sum*fl;
}
template <typename T>
void write(T x){
	static int st[36];
	int top=0;
	if(x<0) putchar('-'),x=-x;
	do{
		st[top++]=x%10,x/=10;
	}while(x);
	while(top) putchar(st[--top]+'0');
}
template <typename T>
void write(T x,char ch){
	write(x);
	putchar(ch);
}

int n,q;
int g,r;
int len[N];
ll tim;
ll ans;
ll wait(ll t){
	ll x=t%(g+r);
	if(x<g) return 0ll;
	else return r+g-x;
}
int vec[N];
int add(int a,int b) {
	return ((a+b)%(g+r)+(g+r))%(g+r);
}
map<int,int> mp;
int f[N];
int ask(int u,int x){
	int y=(--mp.upper_bound(x))->second;
	return len[y]-len[u]+(y==n+1?0:add(-x,-len[y])+f[y]);
}
void update(int l,int r,int x){
	auto L=mp.lower_bound(l),R=--mp.upper_bound(r);
	int y=R->second;
	mp.erase(L,++R);
	mp[l]=x,mp[r]=y;
}
signed main(){
	read(n),read(g),read(r);
	rep(i,1,n+1){
		read(len[i]);
		len[i]+=len[i-1];
//		vec[++vec[0]]=len[i]%(g+r);
	}
	mp[0]=n+1;
//	sort(vec+1,vec+vec[0]+1);
//	vec[0]=unique(vec+1,vec+vec[0]+1)-vec-1;
	for(int i=n;i>=1;i--){
		int ll=add(g,-len[i]),rr=add(0,-len[i]);
		f[i]=ask(i,add(0,-len[i]));
		if(ll<=rr) update(ll,rr,i);
		else update(ll,g+r,i),update(0,rr,i);
	}
	read(q);
	rep(i,1,q){
		read(tim);
		tim=tim^(ans%mod);
		ans=tim+ask(0,add(0,tim));
		write(ans,'\n');
	}
}