主席树

发表于 | 更新于: | 分类于 | | 阅读数

狂补数据结构的知识！！还需慢慢消化🐷主席树的本质就是线段树，叫做可持久化线段树，最为经典的问题就是查询区间第k小的数(说是第k大，HDU2665上面说the kth big number​)，分静态(不带修改)和动态(带修改)两种。

POJ2104||HDU2665(静态)

题意：主席树入门题，题意是查询区间内第k小，主席树入门模板题，可以参考这篇blog。POJ上面的数据好像有点弱，。

每次加入一个新的节点，就要更新线段树，T[i]代表第i颗线段树的根节点，sum[i]表示节点i对应区间的个数，然后根据线段树的性质，左边的子节点总比右边的子节点的数小，那么左边子节点总数就说明左边子节点的最小的数还要小，然后根据左右子节点的个数可以判断出我要找的第k小数在哪个区间内，递归查找就可以了。

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
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
const int maxm=maxn*40;
int T[maxn],L[maxm],R[maxm],sum[maxm];
int sz[maxn],h[maxn]; //sz为原序列,h为离散化之后的序列
int n,q,ql,qr,k,tot;
void build(int& rt,int l,int r){
    rt=++tot;
    sum[rt]=0;
    if(l == r) return ;
    int mid=(l+r)>>1;
    build(L[rt],l,mid);
    build(R[rt],mid+1,r);
}
void update(int& rt,int l,int r,int pre,int x){
    rt=++tot;
    L[rt]=L[pre];
    R[rt]=R[pre];
    sum[rt]=sum[pre]+1;
    if(l == r) return ;
    int mid=(l+r)>>1;
    if(x <= mid) update(L[rt],l,mid,L[pre],x);
    else update(R[rt],mid+1,r,R[pre],x);
}
int query(int s,int e,int l,int r,int k){
    if(l == r) return l;
    int mid=(l+r)>>1;
    int res=sum[L[e]]-sum[L[s]];
    if(k <= res) return query(L[s],L[e],l,mid,k);
    else return query(R[s],R[e],mid+1,r,k-res);
}
int main(){
    scanf("%d %d",&n,&q);
    tot=0;
    for(int i=1; i<=n; i++){
        scanf("%d",&sz[i]);
        h[i]=sz[i];
    }
    sort(h+1,h+1+n);
    int num=unique(h+1,h+1+n)-(h+1);
    build(T[0],1,num);
    for(int i=1; i<=n; i++) update(T[i],1,num,T[i-1],lower_bound(h+1,h+1+num,sz[i])-(h));
    while(q--){
        scanf("%d %d %d",&ql,&qr,&k);
        printf("%d\n",h[query(T[ql-1],T[qr],1,num,k)]);
    }
}

ZOJ-2122.Dynamic Rankings(动态)

题意：动态求区间第k小，可参考blog。

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
104
105
106
#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e4+5;
const int maxm = 1e4+5;
int T[maxn],S[maxn],L[maxn*32],R[maxn*32],sum[maxn*32];
int sz[maxn],h[maxn];
int ul[maxn],ur[maxn];
int tot,num,n,q;
struct node{
    int l,r,k;
    bool flag; //ture代表Q，false代表C
}Q[maxm];  //存储询问
void build(int& rt,int l,int r){
    rt = ++tot;
    sum[rt]=0;
    if(l==r) return;
    int mid = (l+r)>>1;
    build(L[rt],l,mid);
    build(R[rt],mid+1,r);
}
void update(int& rt,int pre,int l,int r,int x,int val){
    rt = ++tot;
    L[rt] = L[pre];
    R[rt] = R[pre];
    sum[rt] = sum[pre]+val;
    if(l==r) return;
    int mid = (l+r)>>1;
    if(x<=mid) update(L[rt],L[pre],l,mid,x,val);
    else update(R[rt],R[pre],mid+1,r,x,val);
}
int lowbit(int x){
    return x&(-x);
}
void add(int x,int val){
    int res = lower_bound(h+1,h+1+num,sz[x])-h;
    while(x<=n){
        update(S[x],S[x],1,num,res,val);
        x += lowbit(x);
    }
}
int Sum(int x,bool flag){
    int res=0;
    while(x>0){
        if(flag) res += sum[L[ur[x]]];
        else res += sum[L[ul[x]]];
        x -= lowbit(x);
    }
    return res;
}
int query(int s,int e,int ts,int te,int l,int r,int k){
    if(l==r) return l;
    int mid = (l+r)>>1;
    int res = Sum(e,true)-Sum(s,false)+sum[L[te]]-sum[L[ts]];
    if(k<=res){
        for(int i=e;i;i-=lowbit(i)) ur[i] = L[ur[i]];
        for(int i=s;i;i-=lowbit(i)) ul[i] = L[ul[i]];
        return query(s,e,L[ts],L[te],l,mid,k);
    }
    else{
        for(int i=e;i;i-=lowbit(i)) ur[i] = R[ur[i]];
        for(int i=s;i;i-=lowbit(i)) ul[i] = R[ul[i]];
        return query(s,e,R[ts],R[te],mid+1,r,k-res);
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        char str[5];
        num=0;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++) scanf("%d",sz+i),h[++num]=sz[i];
        for(int i=1;i<=q;i++){
            scanf("%s",str);
            if(str[0]=='Q'){
                scanf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].k);
                Q[i].flag=true;
            }
            else{
                scanf("%d%d",&Q[i].l,&Q[i].r);
                Q[i].flag=false;
                h[++num]=Q[i].r;
            }
        }
        sort(h+1,h+1+num);
        int tmp = unique(h+1,h+1+num)-h-1;
        num = tmp;
        tot=0;
        build(T[0],1,num);
        for(int i=1;i<=n;i++) update(T[i],T[i-1],1,num,lower_bound(h+1,h+1+num,sz[i])-h,1);
        for(int i=1;i<=n;i++) S[i] = T[0];
        for(int i=1;i<=q;i++){
            if(Q[i].flag){
                for(int j=Q[i].r;j;j-=lowbit(j)) ur[j] = S[j];
                for(int j=Q[i].l-1;j;j-=lowbit(j)) ul[j] = S[j];
                printf("%d\n",h[query(Q[i].l-1,Q[i].r,T[Q[i].l-1],T[Q[i].r],1,num,Q[i].k)]);
            }
            else{
                add(Q[i].l,-1);
                sz[Q[i].l] = Q[i].r;
                add(Q[i].l,1);
            }
        }
    }
    return 0;
}

HDU6703

主席树加set

你有两个操作：$(1,pos)$将$a_{pos}$变成$a_{pos}+10^7$；$(2,r,k)$求$a_1$到$a_r$的一个不存在的值的最小值$x$使得$x\geq k$。

并且强制要求在线做。

直接用主席树在$[1,r]$中跑出一个值，然后利用set存一些被操作的值，因为被操作的值也是备选答案，两者取最小值就好，因为元素都是不重复的，所以这种方法可行。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int n,m;
int op,r,k,pos;
int ans=0;
const int maxm=maxn*40;
int T[maxn],L[maxm],R[maxm],sum[maxm];
set<int>s;
int q,ql,qr,tot;
void build(int& rt,int l,int r){
    rt=++tot;
    sum[rt]=0;
    if(l == r) return ;
    int mid=(l+r)>>1;
    build(L[rt],l,mid);
    build(R[rt],mid+1,r);
}
void update(int& rt,int l,int r,int pre,int x){
    rt=++tot;
    L[rt]=L[pre];
    R[rt]=R[pre];
    sum[rt]=sum[pre]+1;
    if(l == r) return ;
    int mid=(l+r)>>1;
    if(x <= mid) update(L[rt],l,mid,L[pre],x);
    else update(R[rt],mid+1,r,R[pre],x);
}
int Fi;
int ll,rr;
void query(int rt,int l,int r){
    if(Fi < n+1) return ;
    if(l>=ll && r<=rr){
        int res=sum[rt];
        if(res==0){
            Fi=l;
            return ;
        }
        if(sum[rt] == r-l+1) return ;
        int mid=(l+r)>>1;
        if(sum[L[rt]] == mid-l+1) query(R[rt],mid+1,r);
        else query(L[rt],l,mid);
    }
    int mid=(l+r)>>1;
    if(ll<=mid) query(L[rt],l,mid);
    if(rr>mid)  query(R[rt],mid+1,r);
}
int main(){
    int T_T;
    scanf("%d",&T_T);
    while(T_T--){
        ans=0;
        tot=0;
        s.clear();
        scanf("%d %d",&n,&m);
        build(T[0],1,n);
        for(int i=1; i<=n; i++){
            scanf("%d",&a[i]);
            update(T[i],1,n,T[i-1],a[i]);
        }
        while(m--){
            scanf("%d",&op);
            s.insert(n+1); 
            //这个元素必定存在，没有会出错，使得到的的解小，因为lower_bound如果没有找到会返回最后一个值
            if(op == 1){
                scanf("%d",&pos);
                pos^=ans;
                s.insert(a[pos]);
            }
            else{
                scanf("%d %d",&r,&k);
                r^=ans;
                k^=ans;
                Fi=n+1;
                int Fi1=*(s.lower_bound(k));
                ll=k,rr=n;
                query(T[r],1,n);
                ans=min(Fi1,Fi);
                printf("%d\n",ans); 
            }
        }
    }
}
thanks!