「JOISC 2019 Day3」穿越时空 Bitaro-线段树 _线段树

在河狸国，一条路上有N N N 座城市，依次编为1 … N 1\ldots N 1…N 号；连接城市i i i 和城市i + 1 i+1 i+1 的那段路被称为i i i 号路。在河狸国，一天有1 0 9 10^9 109 秒，依次称为时刻0 … 1 0 9 ? 1 0\ldots 10^9-1 0…109?1 。从城市i i i 沿路到达与之相邻的城市——城市i ? 1 i-1 i?1 或城市i + 1 i+1 i+1 需要1 1 1 个单位时间。i i i 号路每天在时刻L i L_i Li? 到时刻R i R_i Ri? 之间开放通行。具体说来，为了通过i i i 号道路，我们必须在满足L i ≤ x ≤ R i ? 1 L_i\le x\le R_i-1 Li?≤x≤Ri??1 的时刻x x x 从城市i i i 或城市i + 1 i+1 i+1 出发，在x + 1 x+1 x+1 时刻到达另一城市。
原本是一位住在河狸国的普通河狸，然而，为了改掉自己迟到的坏习惯，他最终获得了穿越时空的技能。每次使用这个技能，他能回到一秒前。但他不能回到前一天：也就是说，如果他在0 0 0 时刻与1 1 1 时刻之间使用技能，他只能回到这一天的0 0 0 时刻。他只能在城市里使用这个技能。使用这个技能不会改变他的位置。
穿越时空会让变累。为了找到能从一个城市到另一个城市且使用技能次数最少的方法，他决定进行一个Q Q Q 步的想象试验。第j j j 步实验是以下两种情况之一：
他很想知道实验结果。
n ≤ 3 × 1 0 5 n \leq 3 \times 10^5 n≤3×105

文章插图
JOI 的题好清新啊。
先只考虑从左到右的情况，从右到左把整个序列r e v e r s e就行了。
有一个非常自然的想法是把题目放到坐标系上。横坐标代表位置，纵坐标代表时间。发下斜向的移动非常麻烦，考虑把涉及到第i i i 个点的时间全部减去i i i，这样移动时就会变成横线。

文章插图
ps.来自官方题解
考虑修改和查询。可以发现对于临近的两个点i , i + 1 i, i + 1 i,i+1，设它们的时间区域分别是[ a , b ] , [ c , d ] [a,b],[c,d] [a,b],[c,d] 。假设两区间有交，那么[ i , i + 1 ] [i, i+1] [i,i+1] 的时间区域可以看做[ a , b ] , [ c , d ] [a,b],[c,d] [a,b],[c,d] 的交集。
如果无交，这段路径可以表示为一个三元组( a , b , c ) (a,b,c) (a,b,c)，意味着必须先把时间调到a a a 才能走进，然后出来时时间是b b b，中间花费的时间是 c c c 。比如R i < L i + 1 R_i < L_{i+1} Ri? R i + 1 L_i > R_{i+1} Li?>Ri+1?，那么三元组为( L i , R i + 1 , L i ? R i + 1 ) (L_i,R_{i+1},L_i-R_{i+1}) (Li?,Ri+1?,Li??Ri+1?) 。
之后还要考虑三元组/二元组（区间）之间的合并，策略是一样的，即能走就走，否则调时间。
合并显然满足结合率，线段树维护即可。
【「JOISC 2019 Day3」穿越时空 Bitaro-线段树】

#include using namespace std;typedef long long ll;const int maxn = 3e5 + 5;inline int gi(){char c = getchar();while (c < '0' || c > '9') c = getchar();int sum = 0;while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();return sum;}int n, q;int l[maxn], r[maxn], op[maxn], a[maxn], b[maxn], c[maxn], d[maxn];ll ans[maxn];struct node{int op, x, y;ll c;} seq[maxn], val[maxn << 2];node operator + (const node &a, const node &b){if (a.op) {if (b.op) return (node) {1, a.x, b.y, a.c + b.c + max(0, a.y - b.x)};else return (node) {1, a.x, max(b.x, min(b.y, a.y)), a.c + max(0, a.y - b.y)};} else {if (b.op) return (node) {1, min(a.y, max(a.x, b.x)), b.y, b.c + max(0, a.x - b.x)};else if (a.y < b.x) return (node) {1, a.y, b.x, 0};else if (a.x > b.y) return (node) {1, a.x, b.y, a.x - b.y};else return (node) {0, max(a.x, b.x), min(a.y, b.y), 0};}}#define mid ((l + r) >> 1)#define lch (s << 1)#define rch (s << 1 | 1)void build(int s, int l, int r){if (l == r) return val[s] = seq[l], void();build(lch, l, mid);build(rch, mid + 1, r);val[s] = val[lch] + val[rch];}void modify(int s, int l, int r, int p, node v){if (l == r) return val[s] = v, void();if (p <= mid) modify(lch, l, mid, p, v);if (p >= mid + 1) modify(rch, mid + 1, r, p, v);val[s] = val[lch] + val[rch];}node query(int s, int l, int r, int ql, int qr){if (ql <= l && r <= qr) return val[s];if (qr <= mid) return query(lch, l, mid, ql, qr);else if (ql >= mid + 1) return query(rch, mid + 1, r, ql, qr);else return query(lch, l, mid, ql, qr) + query(rch, mid + 1, r, ql, qr);}void reverse(){reverse(l + 1, l + n);reverse(r + 1, r + n);for (int i = 1; i <= q; ++i)if (op[i] == 1) a[i] = n - a[i];else a[i] = n + 1 - a[i], c[i] = n + 1 - c[i];}void solve(){for (int i = 1; i < n; ++i) seq[i] = (node) {0, l[i] - i, r[i] - i - 1, 0};build(1, 1, n - 1);for (int i = 1; i <= q; ++i)if (op[i] == 1) modify(1, 1, n - 1, a[i], (node) {0, b[i] - a[i], c[i] - a[i] - 1, 0});else if (a[i] == c[i]) ans[i] = max(0, b[i] - d[i]);else if (a[i] < c[i]) ans[i] = ((node) {0, b[i] - a[i], b[i] - a[i], 0} + query(1, 1, n - 1, a[i], c[i] - 1) + (node) {d[i] - c[i], d[i] - c[i]}).c;}int main(){n = gi(); q = gi();if (n == 1) {for (int i = 1; i <= q; ++i) {op[i] = gi(), a[i] = gi(), b[i] = gi(), c[i] = gi(), d[i] = op[i] == 2 ? gi() : 0;if (op[i] == 2) printf("%d\n", max(0, b[i] - d[i]));}return 0;}for (int i = 1; i < n; ++i) l[i] = gi(), r[i] = gi();for (int i = 1; i <= q; ++i) op[i] = gi(), a[i] = gi(), b[i] = gi(), c[i] = gi(), d[i] = op[i] == 2 ? gi() : 0;solve();reverse();solve();for (int i = 1; i <= q; ++i) if (op[i] == 2) printf("%lld\n", ans[i]);return 0;}