CF1000F One Occurrence

发表于2020-09-02更新于2023-09-15字数统计642阅读时长6分

One Occurrence

  • 题目链接
  • 数据结构/线段树/可持久化线段树
  • 数据结构/莫队/栈

Description

多次询问区间中只出现一次的任意一个数。

Solution

可持久化线段树做法：
对下标建立可持久化线段树。令 preaipre_{a_i} 表示 aia_i 出现的上一个位置，初始值为 0。如果 aia_i 出现过，则将 preaipre_{a_i} 位置的值修改为 INF。如果一个数在 [l,r][l, r] 只出现了一次，那么在该区间中一定有 pre<lpre < l。对 rootrroot_r 进行区间 [l,r][l, r] 查询返回下标即可。
莫队 + 栈 (惰性删除)：
维护每个数出现次数 cnticnt_i， 如果一个数出现次数等于 1，则将其进栈。如果一个数的出现次数由 1 变为 0 或 变为 2 时，令 deletedi++deleted_i ++，表示删除一次，不直接在栈中操作。查询时，如果栈顶的数 i 的 deletedi>0deleted_i > 0 说明要出栈，一直弹到 deletedi=0deleted_i = 0 为止。

Code

One Occurrence (Persistent Segment Tree)
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
#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 5e5 + 5;

template<typename T>
inline void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct SegTree {
    SegTree * lson, *rson;
    int min = 1e9;
} *root[MAXN], tree[MAXN * 60];
int n, m, pre[MAXN], arr[MAXN];

inline SegTree* newNode (SegTree*& root) {
    static int tot;
    return root = &tree[tot++];
}

inline void build(SegTree* root, int L, int R) {
    if (L == R) return;
    int mid = (L + R) >> 1;
    build(newNode(root->lson), L, mid);
    build(newNode(root->rson), mid + 1, R);
}

inline void modify (SegTree* pre, SegTree*& root, int L, int R, int pos, int val) {
    root = newNode(root), *root = *pre;
    if (L == pos && R == pos) {
        root->min = val;
        return;
    }
    int mid = (L + R) >> 1;
    if (pos <= mid) modify(pre->lson, root->lson, L, mid, pos, val);
    else modify(pre->rson, root->rson, mid + 1, R, pos, val);
    root->min = min(root->lson->min, root->rson->min);
}

inline int query(SegTree* root, int L, int R, int qL, int qR) {
    if (L > qR || R < qL || root->min >= qL) return 0;
    if (L == R) return L;
    int mid = (L + R) >> 1;
    int tmp = query(root->lson, L, mid, qL, qR);
    if (!tmp) return query(root->rson, mid + 1, R, qL, qR);
    return tmp;
}

int main() {
    read(n);
    build(newNode(root[0]), 1, n);
    for (int i = 1; i <= n; i++) {
        read(arr[i]);
        root[i] = root[i - 1];
        if (pre[arr[i]]) modify(root[i], root[i], 1, n, pre[arr[i]], 1e9);
        modify(root[i], root[i], 1, n, i, pre[arr[i]]);
        pre[arr[i]] = i;
    }
    read(m);
    while (m--) {
        int l, r;
        read(l), read(r);
        printf("%d\n", arr[query(root[r], 1, n, l, r)]);
    }
    return 0;
}