Codeforces1000 F. One Occurrence（可持久化线段树）_可持久化线段树经典题目codeforces

题意：

给定长度为n的序列a，
q组询问，每次询问给出[L,R]，
要求输出a[L,R]中任意一个只出现一次的数，
如果没有满足要求的数则输出0。

数据范围：n,q<=5e5，a(i)<=5e5

解法：

用pre[i]表示a[i]上一次出现的位置，
建立线段树，叶子x存pre[x]，这样的话如果[L,R]的pre最小值<L，那么说明存在只出现一次的数。
基本思路是这样，但是这样会存在问题：
如果存在1,1,在线段树中的值分别为0,1,查询[1,2]的时候发现最小值为0，是满足条件的，显然错误。
当区间内存在多个相同的数的时候，应该只存最右边的一个，
那么用可持久化权值线段树做，构造前缀树，
在插入的时候，如果存在pre则先将pre删除(修改为inf)，然后再插入。

同时维护区间最小值即可。
找[l,r]的答案就找Rt[r]中[l,r]的pre最小值所在的位置(下标)即可。

code：

#include<bits/stdc++.h>
using namespace std;
const int maxm=5e5+5;
int pre[maxm];
int a[maxm];
int n;
struct Tree{
    int lc[maxm*40*2],rc[maxm*40*2],mi[maxm*40*2];
    int rt[maxm*2],tot;
    void pp(int k){
        mi[k]=min(mi[lc[k]],mi[rc[k]]);
    }
    void update(int x,int val,int l,int r,int last,int &k){
        k=++tot;
        lc[k]=lc[last],rc[k]=rc[last],mi[k]=mi[last];
        if(l==r){
            mi[k]=val;
            return ;
        }
        int mid=(l+r)/2;
        if(x<=mid)update(x,val,l,mid,lc[last],lc[k]);
        else update(x,val,mid+1,r,rc[last],rc[k]);
        pp(k);
    }
    int askmi(int st,int ed,int l,int r,int k){
        if(!k)return 1e9;
        if(st<=l&&ed>=r)return mi[k];
        int mid=(l+r)/2;
        int ans=1e9;
        if(st<=mid)ans=min(ans,askmi(st,ed,l,mid,lc[k]));
        if(ed>mid)ans=min(ans,askmi(st,ed,mid+1,r,rc[k]));
        return ans;
    }
    int get(int st,int ed,int l,int r,int k){
        if(!k)return 0;
        if(mi[k]>=st)return 0;
        if(l==r)return l;
        int mid=(l+r)/2;
        int ans=0;
        if(st<=mid)ans=get(st,ed,l,mid,lc[k]);
        if(!ans&&ed>mid)ans=get(st,ed,mid+1,r,rc[k]);
        return ans;
    }
}T;
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        T.update(i,1e9,1,n,T.rt[0],T.rt[0]);
    }
    for(int i=1;i<=n;i++){
        T.rt[i]=T.rt[i-1];
        if(pre[a[i]]){//del pre[a[i]]
            T.update(pre[a[i]],1e9,1,n,T.rt[i],T.rt[i]);
        }
        T.update(i,pre[a[i]],1,n,T.rt[i],T.rt[i]);
        pre[a[i]]=i;
    }
    int q;scanf("%d",&q);
    while(q--){
        int l,r;scanf("%d%d",&l,&r);
        int mi=T.askmi(l,r,1,n,T.rt[r]);
        if(mi>=l){
            puts("0");
        }else{
            int pos=T.get(l,r,1,n,T.rt[r]);
            printf("%d\n",a[pos]);
        }
    }
    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