「Codeforces 187D」BRT Contract【线段树】

Description

泰迪每天都要通过一条路从家到学校,这条路的起点是泰迪家,终点是学校。

这条路中间还有 nn 个路口,从第 i1i - 1 个路口走到第 ii 个路口需要 did_i 秒,每个路口都有一个红绿灯。更具体地,绿灯持续时间是 gg 秒,红灯持续时间是 rr 秒。每天从第 00 秒开始,所有灯都是绿灯,持续 gg 秒之后变为红灯,再过 rr 秒变成绿灯,以此类推,并且同一时刻所有灯都是相同状态。

当泰迪到达一个路口,若是绿灯则可直接通过,若是红灯则需原地等待至绿灯。若到达某一路口时灯的状态正好发生改变,则视到达路口时灯的颜色为其改变后的颜色,例如第 gg 秒到达一个路口则视为遇到红灯。

现在泰迪预计了接下来 qq 天从家出发的时间,第 jj 天将会在第 tjt_j 秒从家出发,请告诉他每天到达学校的最早时间。假定一天内泰迪一定可以到达学校。

Input

第一行包含三个整数 n,g,rn, g, r (1n105,(1 \leqslant n \leqslant 10^5, 2g+r109)2 \leqslant g + r \leqslant 10^9),表示路口数和两种灯的持续时间。

第二行包含 n+1n + 1 个正整数 did_i (1di109)(1 \leqslant d_i \leqslant 10^9),表示相邻路口间的通行时间。另外 d1d_1 表示从起点到第一个路口的所需时间,dn+1d_{n + 1} 表示第 nn 个路口到终点的所需时间。

第三行包含一个正整数 qq (1q105)(1 \leqslant q \leqslant 10^5),表示询问天数。

接下来 qq 行,每行包含一个非负整数 tjt_j (1tj109)(1 \leqslant t_j \leqslant 10^9),表示第 jj 天的出发时间。

Output

对于每个询问输出一行一个整数表示答案。

Sample Input

1
2
3
4
5
6
7
8
1 3 2
5 2
5
1
2
3
4
5

Sample Output

1
2
3
4
5
8
9
12
12
12

Solution

将时间按模 g+rg + r 进行考虑。考虑从起点出发,若到达一个路口时碰到红灯无法通过,则会等到绿灯后立即通过,剩余所需时间等于从该路口第 00 秒出发到达终点的时间。

问题转化为求从起点出发,遇到第一个红灯时所在的路口,以及求从第 ii 个路口第 00 秒出发到达终点所需时间 ((设为 fi)f_i)。求 fif_i 与求解询问的做法无异,因此考虑从 nn 开始倒推 fif_i,剩余问题转化为求遇到的第一个红灯路口。

因为遇到第一个红灯前全部经过绿灯,所以所需时间为两个路口间的距离,遇上红灯说明时间 tt 在模 g+rg + r 意义下在区间 [g,g+r)[g, g + r) 中。

用权值线段树维护修改与询问即可,时间复杂度为 O(nlogn)O(n \log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 200010;
int n, q, g, r, tot, d[maxn], rt[maxn];
ll sum, f[maxn];
struct node { int l, r, v; } t[maxn * 20];

void modify(int &k1, int k2, int l, int r, int p, int v) {
t[k1 = ++tot] = t[k2], t[k1].v = v;
if (l == r) return; int mid = (l + r) >> 1;
if (mid >= p) modify(t[k1].l, t[k2].l, l, mid, p, v);
else modify(t[k1].r, t[k2].r, mid + 1, r, p, v);
}

int query(int k, int l, int r, int ql, int qr) {
if (!k) return n;
if (l == ql && r == qr) return t[k].v;
int mid = (l + r) >> 1;
if (mid >= qr) return query(t[k].l, l, mid, ql, qr);
else if (mid < ql) return query(t[k].r, mid + 1, r, ql, qr);
else return min(query(t[k].l, l, mid, ql, mid), query(t[k].r, mid + 1, r, mid + 1, qr));
}

int main() {
scanf("%d %d %d", &n, &g, &r), n++;
for (int i = 1; i <= n; i++) {
scanf("%d", &d[i]), sum += d[i];
d[i] = (d[i] + d[i - 1]) % (g + r);
}
for (int i = n; i >= 0; i--) {
modify(rt[i], rt[i + 1], 0, g + r - 1, d[i], i);
}
for (int i = n - 1, t, p1, p2, p; i >= 0; i--) {
t = g + r - d[i];
p1 = query(rt[i + 1], 0, g + r - 1, max(g - t, 0), g + r - 1 - t);
p2 = g < t ? query(rt[i + 1], 0, g + r - 1, g + g + r - t, g + r - 1) : n;
p = min(p1, p2);
f[i] = p == n ? 0 : f[p] + (g + r - (0LL + d[p] + t) % (g + r)) % (g + r);
}
scanf("%d", &q);
for (int i = 1, x, t, p1, p2, p; i <= q; i++) {
scanf("%d", &x), t = x % (g + r);
p1 = query(rt[1], 0, g + r - 1, max(g - t, 0), g + r - 1 - t);
p2 = g < t ? query(rt[1], 0, g + r - 1, g + g + r - t, g + r - 1) : n;
p = min(p1, p2);
ll k = p == n ? 0 : f[p] + (g + r - (0LL + d[p] + t) % (g + r)) % (g + r);
printf("%lld\n", x + sum + k);
}
return 0;
}