CF187D BRT Contract 题解
题目链接：CF187D BRT Contract
题意：
cxy 每天都要通过一条路从家到学校，这条路的起点是 cxy 家，终点则是学校。
这条路中间还有 $n$ 个路口，从第 $i - 1$ 个路口走到第 $i$ 个路口需要 $d_i$ 秒，每个路口都有一个红绿灯。
更具体地，绿灯持续时间是 $g$ 秒，红灯持续时间是 $r$ 秒。每天从第 $0$ 秒开始，所有灯都是绿灯，持续 $g$ 秒之后变为红灯，再过 $r$ 秒变成绿灯，以此类推，并且同一时刻所有灯都是相同状态。
当cxy到达一个路口，若是绿灯则可直接通过，若是红灯则需原地等待至绿灯。
若到达某一路口时灯的状态正好发生改变，则视到达路口时灯的颜色为其改变后的颜色，例如第 $g$ 秒到达一个路口则视为遇到红灯。
现在 cxy 预计了接下来 $q$ 天从家出发的时间，第 $j$ 天将会在第 $t_j$ 秒从家出发，她希望你告诉她每天到达学校的最早时间。你可以假定一天内 cxy 一定可以到达学校。
输入格式：
The first line of input contains three space-separated positive integers $n,g,r(1\le n\le 10^{5},~2\le g+r\le 10^{9})$ — the number of intersections, duration of green phase and duration of red phase. Next line contains $n+1$ integers $l_{i}(1\le l_{i}\le 10^{9})$ — the time to pass the $i$ -th road segment in the path from source to destination.
Next line contains a single integer $q(1\le q\le 10^{5})$ — the number of buses in a day. The $i$ -th of next $q$ lines contains a single integer $t_{i}(1\le t_{i}\le 10^{9})$ — the time when $i$ -th bus leaves the source station.
输出格式：
In the $i$ -th line of output you should print a single integer — the time that $i$ -th bus gets to destination.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.
数据范围：
保证 $1\leq n, q \leq 10^5, ~2 \leq g+r \leq 10^9,~ 1\le d_i, t_j \leq 10^9$。
注意到是否会在红绿灯停下只与当前时刻 $\bmod (g + r)$ 的值有关
并且在一次停下后，这个值会暂时清零。不妨设 $f_i$ 表示 $0$ 时刻从 $i$ 出发的花费。
不过首先我们要解决的问题是：如何找到第一个需要等红灯的位置呢？
设从开始到第 $i$ 个位置的距离模 $(g + r)$ 的余数为 $p$ ，出发的时间为 $t$
若满足 $g \le (t + p) \bmod (g + r)$ ，则会在 $i$ 处停下。 $p$ 是固定的，我们看看 $t$ 的范围：
所以在这些范围的 $t$ 都会在 $i$ 停下。这个可以用动态开点线段树维护（区间推平+单点查）
那么 $f_i$ 怎么计算呢？我们假设没有经过红灯直接到达 $i$ 。
考虑以该方式查询：在家等 $q$ 秒到绿灯，这等价于时刻 $0$ ，最后花费时间减去从家到 $i$ 和等的 $q$ 即可。
时间复杂度 $\mathcal{O}(n \log m)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e6 + 15))
#define ls(at) ch[at][0]
#define rs(at) ch[at][1]
signed tot = 1, ch[N * 8][2], val[N * 8];
int n,m,G,R,Q,rt = 1,d[N],X[N],f[N];
void push_down(int at,int len)
{
if(val[at] && len > 1)
{
if(!ls(at)) ls(at) = ++tot;
if(!rs(at)) rs(at) = ++tot;
val[ls(at)] = val[rs(at)] = val[at]; val[at] = 0;
}
}
void update(int l,int r,int at,int nl,int nr,int k)
{
push_down(at, r - l + 1);
if(nl <= l && r <= nr) { val[at] = k; push_down(at, r - l + 1); }
else
{
int mid = (l + r) >> 1;
if(nl <= mid) update(l,mid,ls(at),nl,nr,k);
if(nr > mid) update(mid+1,r,rs(at),nl,nr,k);
}
}
int query(int l,int r,int at,int x)
{
push_down(at, r - l + 1);
if(l == r) return val[at];
int mid = (l + r) >> 1;
if(x <= mid) return query(l,mid,ls(at),x);
else return query(mid+1,r,rs(at),x);
}
int Query(int t)
{
int p = query(0,m-1,rt,t%m);
int res = t + X[p] + f[p];
if(p <= n) res += m - (X[p] + t) % m;
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> G >> R; m = G + R;
for(int i = 1; i <= n + 1; i++) { cin >> d[i]; X[i] = X[i - 1] + d[i]; }
update(0, m - 1, rt, 0, m - 1, n + 1);
for(int i = n, p = 0; i >= 1; i--)
{
p = m - X[i] % m; f[i] = Query(p) - X[i] - p; p = X[i] % m;
if(p <= G) update(0, m - 1, rt, G - p, m - 1 - p, i);
else { update(0, m - 1, rt, 0, m - 1 - p, i), update(0, m - 1, rt, m - p + G, m - 1, i); }
}int _Q;
cin >> _Q; for(int x; _Q--; ) { cin >> x; cout << Query(x) << '\n'; }
return 0;
}参考文献：