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

Description

在河狸国，一条路上有 $N$ 座城市，依次编为 $1\dots N$ 号；连接城市 $i$ 和城市 $i+1$ 的那段路被称为 $i$ 号路。在河狸国，一天有 $10^9$ 秒，依次称为时刻 $0\dots 10^9-1$。从城市 $i$ 沿路到达与之相邻的城市——城市 $i-1$ 或城市 $i+1$ 需要 $1$ 个单位时间。$i$ 号路每天在时刻 $L_i$ 到时刻 $R_i$ 之间开放通行。具体说来，为了通过 $i$ 号道路，我们必须在满足 $L_i\le x\le R_i-1$ 的时刻 $x$ 从城市 $i$ 或城市 $i+1$ 出发，在 $x+1$ 时刻到达另一城市。

Bitaro 原本是一位住在河狸国的普通河狸，然而，为了改掉自己迟到的坏习惯，他最终获得了穿越时空的技能。每次使用这个技能，他能回到一秒前。但他不能回到前一天：也就是说，如果他在 $0$ 时刻与 $1$ 时刻之间使用技能，他只能回到这一天的 $0$ 时刻。他只能在城市里使用这个技能。使用这个技能不会改变他的位置。

穿越时空会让 Birato 变累。为了找到能从一个城市到另一个城市且使用技能次数最少的方法，他决定进行一个 $Q$ 步的想象试验。第 $j$ 步实验是以下两种情况之一：

• 改变 $P_j$ 号道路的开放时间，改后 $P_j$ 号道路在时刻 $S_j$ 到时刻 $E_j$ 开放通行；
• 假设时刻 $B_j$ 他在城市 $A_j$，然后计算在这一天的时刻 $D_j$ 他要到达城市 $C_j$ 的话至少需要使用多少次技能。

他很想知道实验结果。

$n\le 3\times 10^5$

Solution

JOI 的题好清新啊。

先只考虑从左到右的情况，从右到左把整个序列 $reverse$ 就行了。

有一个非常自然的想法是把题目放到坐标系上。横坐标代表位置，纵坐标代表时间。发下斜向的移动非常麻烦，考虑把涉及到第 $i$ 个点的时间全部减去 $i$，这样移动时就会变成横线。

ps.来自官方题解

考虑修改和查询。可以发现对于临近的两个点 $i,i+1$，设它们的时间区域分别是 $[a,b],[c,d]$。假设两区间有交，那么 $[i,i+1]$ 的时间区域可以看做 $[a,b],[c,d]$ 的交集。

如果无交，这段路径可以表示为一个三元组 $(a,b,c)$，意味着必须先把时间调到 $a$ 才能走进，然后出来时时间是 $b$，中间花费的时间是$c$。比如 $R_i<L_{i+1}$，那么三元组为 $(R_i,L_{i+1},0)$；如果 $L_i>R_{i+1}$，那么三元组为 $(L_i,R_{i+1},L_i-R_{i+1})$。

之后还要考虑三元组/二元组（区间）之间的合并，策略是一样的，即能走就走，否则调时间。

合并显然满足结合率，线段树维护即可。

#include <bits/stdc++.h>
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;
}