「JOISC 2019 Day3」穿越时空 Bitaro

「JOISC 2019 Day3」穿越时空 Bitaro

Description

在河狸国，一条路上有 N N N 座城市，依次编为 1 … N 1ldots 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 0ldots 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_ile xle 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 时刻到达另一城市。

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

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

• 改变 P j P_j Pj​ 号道路的开放时间，改后 P j P_j Pj​ 号道路在时刻 S j S_j Sj​ 到时刻 E j E_j Ej​ 开放通行；
• 假设时刻 B j B_j Bj​ 他在城市 A j A_j Aj​，然后计算在这一天的时刻 D j D_j Dj​ 他要到达城市 C j C_j Cj​ 的话至少需要使用多少次技能。

他很想知道实验结果。

n ≤ 3 × 1 0 5 n leq 3 times 10^5 n≤3×105

Solution

JOI 的题好清新啊。

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

有一个非常自然的想法是把题目放到坐标系上。横坐标代表位置，纵坐标代表时间。发下斜向的移动非常麻烦，考虑把涉及到第 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​<Li+1​，那么三元组为 ( R i , L i + 1 , 0 ) (R_i,L_{i+1},0) (Ri​,Li+1​,0)；如果 L i > 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​)。

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

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

#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("%dn", 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("%lldn", ans[i]);return 0;
}