Problem
泰迪每天都要通过一条路从家到学校，这条路的起点是泰迪家，终点则是学校。
这条路中间还有 \(n\) 个路口，从第 \(i - 1\) 个路口走到第 \(i\) 个路口需要 \(d_i\) 秒，每个路口都有一个红绿灯。更具体地，绿灯持续时间是 \(g\) 秒，红灯持续时间是 \(r\) 秒。每天从第 \(0\) 秒开始，所有灯都是绿灯，持续 \(g\) 秒之后变为红灯，再过 \(r\) 秒变成绿灯，以此类推，并且同一时刻所有灯都是相同状态。当泰迪到达一个路口，若是绿灯则可直接通过，若是红灯则需原地等待至绿灯。若到达某一路口时灯的状态正好发生改变，则视到达路口时灯的颜色为其改变后的颜色，例如第 \(g\) 秒到达一个路口则视为遇到红灯。
现在泰迪预计了接下来 \(q\) 天从家出发的时间，第 \(j\) 天将会在第 \(t_j\) 秒从家出发，他希望你告诉他每天到达学校的最早时间。你可以假定一天内泰迪一定可以到达学校。
保证 \(n, q \leq 10^5, 2 \leq g, r \leq 10^9, d_i, t_j \leq 10^9\)。
Input
一行三个整数 \(n,g,r\)。
一行 \(n+1\) 个整数 \(d_i\)，表示从第 \(i-1\) 到第 \(i\) 个需要的时间，注意，第 \(0\) 个路口是家，第 \(n+1\) 个路口是学校。
一行一个整数 \(q\)，表示询问数。
\(q\) 行，每行一个整数 \(t_j\)表示出发时间。
Output
\(q\) 行，表示最早到达学校的时间。
Sample
Input 1
1 3 2
5 2
5
1
2
3
4
5
Output 1
8
9
12
12
12
Input 2
5 3 7
10 1 1 8 900000005 1000000000
3
1
10
1000000000
Output 2
1900000040
1900000040
2900000030
Solution
首先如果直接模拟是肯定不可行的，所以一定存在一个优美的性质。不难发现因为所有红绿灯都是同步的，所以一旦在某一位置停下来等红灯，后续的时间开销是固定的。
于是考虑预处理这一部分，定义 \(f_i\) 表示从第 \(i\) 个位置出发，起始时刚好绿灯亮起，到终点的时间。然后转移，我们要找到 \(i\) 后第一个等红灯的位置，记为 \(j\)。
-
如果 \(j = n + 1\)，说明不需要等红灯，\(f_i = Dis(i,n + 1)\)，\(i\) 到 \(n+1\) 的距离可以前缀和作差得到。
-
如果 \(j \neq n+1\)，说明 \(i\) 后第一次等红灯的位置是 \(j\)，那么 \(j\) 满足 \(Dis(i,j)\) 对 \((g+r)\) 取模后的值 \(\geq g\)。显然，使 \((t+f_i)\) 对 \((g+r)\) 取模后的值 \(\geq g\) 的 \(t\) 的范围是区间，可以用线段树进行区间查询。对于已经计算过的 \(f\) 值，将它插入线段树中，便于后续计算。
对于每一个询问的时间 \(t\)，我们可以区间查询找到第一个等红灯的位置 \(i\)，那么答案就是 \(t + Dis(0,i) + t' + f_i\)，其中 \(t'\) 表示在第 \(i\) 个位置等红灯的时间。
注意到值域很大，线段树要使用动态开点。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int kmax = 1e6 + 3;
struct T {
int ls, rs;
int s;
} tr[kmax * 5];
long long n, m, t, s[kmax];
long long g, r, mod;
int ct, rt;
long long f[kmax];
int Add() {
tr[++ct].s = n + 1; // 初始化
return ct;
}
void Pushup(int x) {
if(!tr[x].ls) tr[x].ls = Add();
if(!tr[x].rs) tr[x].rs = Add();
tr[x].s = min(tr[tr[x].ls].s, tr[tr[x].rs].s);
}
void Modify(int &x, int l, int r, int k, int v) {
if(!x) x = Add(); // 动态开点
if(l == r) {
tr[x].s = v;
return;
}
int mid = (l + r) >> 1;
if(k <= mid) {
Modify(tr[x].ls, l, mid, k, v);
} else {
Modify(tr[x].rs, mid + 1, r, k, v);
}
Pushup(x);
}
int Query(int x, int l, int r, int _l, int _r) {
if(!x) return n + 1; // 没有这个节点
if(_l <= l && r <= _r) return tr[x].s;
int tot = n + 1;
int mid = (l + r) >> 1;
if(_l <= mid) tot = min(tot, Query(tr[x].ls, l, mid, _l, _r));
if(_r > mid) tot = min(tot, Query(tr[x].rs, mid + 1, r, _l, _r));
return tot;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> g >> r;
mod = g + r; // 灯的周期
for(int i = 1; i <= n + 1; i++) {
cin >> s[i];
s[i] += s[i - 1]; // 求前缀
}
for(int i = n, j; i; i--) {
t = mod - s[i] % mod;
if(g >= t) {
j = Query(rt, 0, mod - 1, g - t, mod - 1 - t);
} else {
j = min(Query(rt, 0, mod - 1, 0, mod - 1 - t), Query(rt, 0, mod - 1, g - t + mod, mod - 1));
}
if(j == n + 1) {
f[i] = s[n + 1] - s[i]; // 没有红灯
} else {
f[i] = f[j] + s[j] - s[i] + mod - (s[j] - s[i]) % mod; // 有红灯
}
Modify(rt, 0, mod - 1, s[i] % mod, i); // 单点修改
// cout << i << ' ' << f[i] << '\n';
}
cin >> m;
for(int i = 1, j, x; i <= m; i++) {
cin >> x;
t = x % mod;
if(g >= t) {
j = Query(rt, 0, mod - 1, g - t, mod - 1 - t);
} else {
j = min(Query(rt, 0, mod - 1, 0, mod - 1 - t), Query(rt, 0, mod - 1, g - t + mod, mod - 1)); // 两个区间
}
if(j == n + 1) {
cout << x + s[n + 1] << '\n'; // 没有红灯
} else {
cout << x + s[j] + f[j] + mod - (s[j] + x) % mod << '\n'; // 有红灯
}
}
return 0;
}