计蒜客41384 - so easy

发表于 更新于 分类于 阅读次数：

题目链接：ICPC 2019 徐州赛区网络赛 B

所有的答案只可能是\(x_i\)和\(x_i + 1\)，对这些点离散化之后，使用并查集维护从当前点开始向右第一个合法位置，合并的时候向右合并即可。

渐进时间复杂度\(O(q \cdot \alpha(2n))\)。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 2000000 + 5;
int n, q, z[MAX_N], x[MAX_N], d[MAX_N], tot;
int f[MAX_N];
void init() {
    for (int i = 1; i <= tot; ++i) f[i] = i;
}
int find(int u) {
    return u == f[u] ? u : f[u] = find(f[u]);
}
inline int merge(int u, int v) {
    f[find(u)] = find(v);
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= q; ++i) {
        scanf("%d%d", z + i, x + i);
        d[++tot] = x[i];
        d[++tot] = x[i] + 1;
    }
    sort(d + 1, d + tot + 1);
    tot = unique(d + 1, d + tot + 1) - d - 1;
    init();
    for (int i = 1; i <= q; ++i) {****
        if (z[i] == 1) {
            int pos = lower_bound(d + 1, d + tot + 1, x[i]) - d;
            int nex = lower_bound(d + 1, d + tot + 1, x[i] + 1) - d;
            merge(pos, nex);
        } else {
            int pos = lower_bound(d + 1, d + tot + 1, x[i]) - d;
            int u = find(pos);
            printf("%d\n", d[u] <= n ? d[u] : -1);
        }
    }
    return 0;
}