[Codeforces319E] Ping-Pong

做法

题目中的连边方式可以概括为,如果(开)区间 \((l_1,r_1)\)\((l_2,r_2)\) 交不为空,且 \((l_1,r_1)\)\((l_2,r_2)\) 不是一对存在包含关系的区间,那么这两个区间之间有一条双向边。否则,如果 \((l_1,r_1)\)\((l_2,r_2)\) 包含,\((l_1,r_1)\)\((l_2,r_2)\) 有一条有向边。

对于一个仅由双向边构成的连通块,设这个连通块中所有区间的并为 \((L,R)\),我们可以认为现在就存在这样一个区间 \((L,R)\)。因为长度是递增的,如果之后加入一个区间 \((a,b)\)\(a\)\((L,R)\) 包含或者 \(b\)\((L,R)\) 包含,那么 \((a,b)\) 与这个连通块中的某个点有一条双向边。不难发现,一个区间 \(a\) 能到达区间 \(b\) 的充要条件是 \(a\) 所在连通块所有区间的并被 \(b\) 所在连通块所有区间的并包含。这样我们只要用并查集维护连通块,并记录一下连通块的并的左右端点,就可以直接判断能否到达了。

我们用线段树维护,对于每个点有哪些连通块的并包含这个点。这可以通过在线段树上每个点开一个 vector 来实现,查询哪些连通块的并包含一个点时,只需取这个点到根的路径上所有 vector 的并即可。每加入一个区间,就对左右端点查一下,把得到的连通块合并,然后再把新的连通块加入线段树。由于所有被你查过的点 vector 中所有点都会被你合并,所以你每查询一个点的 vector 就可以把它的 vector 清空,而每加入一个区间最多增加一个连通块,你只会给 \(\mathcal O(\log n)\) 个点的 vector 添加元素。所以这个算法的总复杂度为 \(\mathcal O(n \log n \alpha (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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010*2;
const int maxw = 1e9;

vector<int> tmp;

int n, c;
int L[maxn], R[maxn], fa[maxn];
int qo[maxn], qx[maxn], qy[maxn];

vector<int> T[maxn<<2];
vector<int> vres;

int getroot(int x) {
if (x == fa[x]) return x;
return fa[x] = getroot(fa[x]);
}

void upd(int L, int R, int x, int l, int r, int rt) {
if (L > R) return;
if (L <= l && r <= R) {
T[rt].push_back(x);
return;
}
int m = (l + r) >> 1;
if (L <= m) upd(L, R, x, l, m, rt<<1);
if (R > m) upd(L, R, x, m+1, r, rt<<1|1);
}


void qry(int p, int l, int r, int rt) {
vres.insert(vres.end(), T[rt].begin(), T[rt].end());
T[rt].clear();
if (l == r) return;
int m = (l + r) >> 1;
if (p <= m) qry(p, l, m, rt<<1);
else qry(p, m+1, r, rt<<1|1);
}

// x 是根,把 y 加入 x
void Union(int x, int y) {
int ry = getroot(y);
fa[ry] = x;
L[x] = min(L[x], L[ry]);
R[x] = max(R[x], R[ry]);
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &qo[i], &qx[i], &qy[i]);
if (qo[i] == 1) {
tmp.push_back(qx[i]), tmp.push_back(qy[i]);
}
}
sort(tmp.begin(), tmp.end());
for (int i = 1; i <= n; i++) {
if (qo[i] == 1) {
qx[i] = int (lower_bound(tmp.begin(), tmp.end(), qx[i]) - tmp.begin() + 1);
qy[i] = int (lower_bound(tmp.begin(), tmp.end(), qy[i]) - tmp.begin() + 1);
++ c;
L[c] = qx[i], R[c] = qy[i];
fa[c] = c;
}
}
int _c = 0;
for (int i = 1; i <= n; i++) {
if (qo[i] == 1) {
++ _c;
vres.clear();
int l = qx[i], r = qy[i];
qry(l, 1, 2*n, 1), qry(r, 1, 2*n, 1);
for (int i = 0; i < vres.size(); i++) Union(_c, vres[i]);
upd(L[_c]+1, R[_c]-1, _c, 1, 2*n, 1);
} else {
int rx = getroot(qx[i]), ry = getroot(qy[i]);
if (L[rx] >= L[ry] && R[rx] <= R[ry]) puts("YES");
else puts("NO");
}
}
return 0;
}