26.CF1000F One Occurrence

26.CF1000F One Occurrence

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定序列，要求支持查询区间内只出现一次的数字

可以离线，那么离线所有询问后按右端点排序，然后加入贡献回答即可。

洛谷传送门：CF1000F One Occurrence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：F. One Occurrence (codeforces.com)

题目思路

给定序列，要求支持查询区间内只出现一次的数字。

这属于一类特别典型的问题：开桶维护最后一次出现位置，在更新时去重复贡献。

对于本题，我们首先对所有询问进行离线，然后按照右端点排序加入贡献计算答案：

• 记录每个数字上次最后一次出现的位置
• 只要对于上一次出现的位置维护一个区间最小值和最小值的数值，然后查询区间最小值是否位于区间内即可
• 在每次加入右端点时判断是否之前出现过，如果出现过就清除上次加入的贡献(当当前点为右端点时，上次出现的位置一定只能作为左端点出现，因此需要消除其作为右端点时记录的前序信息)

当然，这题如果强制在线的话，可以用可持久化权值线段树保留历史版本进行查询。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 4e6 + 10;

namespace SegTree{
    #define ls rt << 1
    #define rs rt << 1 | 1
    #define lson ls, l, mid
    #define rson rs, mid + 1, r

    struct Info{
        int val, pre;
        Info operator+ (Info x) {
            Info ans = {val, pre};
            if(pre > x.pre) ans.pre = x.pre, ans.val = x.val;
            return ans;
        }
    }tree[N];

    inline void push_up(int rt){
        tree[rt] = tree[ls] + tree[rs];
    }

    void build(int rt, int l, int r){
        tree[rt] = {0, INT_MAX};
        if(l == r) return;
        int mid = l + r >> 1;
        build(lson), build(rson);
    }

    void update(int rt, int l, int r, int pos, int val, int pre){
        if(l == r) return (void)(tree[rt] = Info{val, pre});
        int mid = l + r >> 1;
        if(mid >= pos) update(lson, pos, val, pre);
        else update(rson, pos, val, pre);
        push_up(rt);
    }


    Info query(int rt, int l, int r, int L, int R){
        if(l >= L && r <= R) return tree[rt];
        int mid = l + r >> 1; Info ans = Info{0, INT_MAX};
        if(mid >= L) ans = ans + query(lson, L, R);
        if(mid < R) ans = ans + query(rson, L, R);
        return ans;
    }

    #undef ls
    #undef rs
    #undef lson
    #undef rson
}

struct query{
    int l, id;
    const bool operator< (const query &x) const { return l < x.l; }
};

vector<query> q[N];

int a[N], ans[N], last[N];


inline void solve(){
    int n = 0; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    SegTree::build(1, 1, n);
    int m = 0; cin >> m;
    for(int i = 1; i <= m; i++){
        int l, r; cin >> l >> r;
        q[r].emplace_back(query{l, i});
    }

    for(int i = 1; i <= n; i++){
        if(last[a[i]]){
            SegTree::update(1, 1, n, last[a[i]], 0, INT_MAX);
            SegTree::update(1, 1, n, i, a[i], last[a[i]]);
        }
        else SegTree::update(1, 1, n, i, a[i], 0);
        last[a[i]] = i;

        for(auto qu : q[i]){
            assert(qu.l <= i);
            auto res = SegTree::query(1, 1, n, qu.l, i);
            if(res.pre < qu.l) ans[qu.id] = res.val;
            else ans[qu.id] = 0; 
        }
    }

    for(int i = 1; i <= m; i++) cout << ans[i] << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103