treap(可持久性)模板

Posted on | In

普通treap：

参考https://www.csdn.net/gather_2a/MtTacg3sMTE0NS1ibG9n.html

cf702f：

将所有人的钱数放入平衡树，每次按照可选衣服的价格将树一分为二，对于有购买能力的一棵树上的人钱数减去衣服价格，然后将剩余钱数小于c-1的再塞回第一棵树，最后将这两棵树合并。由于是非持久性结构，所有的人的节点编号不会变，会变的只有他们的亲子关系，所以可以直接用一个数组记录每个人的剩余钱数和已购买的衣服数量。

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
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
#define N 210000
#define ls ch[now][0]
#define rs ch[now][1]
int n,m,root;
pair<int,int>a[N];
int val[N],ch[N][2],lzy_val[N],lzy_cnt[N],rnd[N],cnt[N];
void pushdown(int now){	//将修改的根节点的值扩散下去
    if(!now)
        return;
    if(lzy_val[now]){
        val[ls]+=lzy_val[now];val[rs]+=lzy_val[now];
        lzy_val[ls]+=lzy_val[now];lzy_val[rs]+=lzy_val[now];
        lzy_val[now]=0;
    }
    if(lzy_cnt[now]){
        cnt[ls]+=lzy_cnt[now];cnt[rs]+=lzy_cnt[now];
        lzy_cnt[ls]+=lzy_cnt[now];lzy_cnt[rs]+=lzy_cnt[now];
        lzy_cnt[now]=0;
    }
}
/*
void pushup(int now){
    siz[now]=siz[ls]+siz[rs]+1;
}
*/
//按值split,如果按树的规模split需要再pushup一次
void split(int rt,int &x,int &y,int v){
    if(!rt){ x=y=0;return;}
    pushdown(rt);
    if(val[rt]<=v){
        x=rt;
        split(ch[rt][1],ch[x][1],y,v);
    }else{
        y=rt;
        split(ch[rt][0],x,ch[y][0],v);
    }
}
int merge(int x,int y){
    if(!x||!y)
        return x+y;
    if(rnd[x]<rnd[y]){
        pushdown(x);
        ch[x][1]=merge(ch[x][1],y);
        //pushup(x);
        return x;
    }else{
        pushdown(y);
        ch[y][0]=merge(x,ch[y][0]);
        //pushup(y);
        return y;
    }
}
int insert(int rt,int x){
    int r1=0,r2=0;
    split(rt,r1,r2,val[x]);
    r1=merge(r1,x);
    rt=merge(r1,r2);
    return rt;
}

void down(int now){
    if(!now)
        return;
    pushdown(now);
    down(ls);down(rs);
}
int main(){
    scanf("%d",&n);
    for(int i=1,c,q;i<=n;i++){
        scanf("%d%d",&c,&q);
        a[i]=make_pair(-q,c);
    }
    sort(a+1,a+1+n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&val[i]);
        rnd[i]=rand();
        root=insert(root,i);
    }
    for(int i=1;i<=n;i++){
        int c=a[i].second;
        int r1=0,r2=0,r3=0,r4=0;
        split(root,r1,r2,c-1);
        val[r2]-=c;lzy_val[r2]-=c;
        cnt[r2]++;lzy_cnt[r2]++;
        split(r2,r3,r4,c-2);
        queue<int> q;
        q.push(r3);
        while(!q.empty()){
            int now=q.front();
            pushdown(now);
            q.pop();
            if(ls){
                q.push(ls);
                ls=0;
            }
            if(rs){
                q.push(rs);
                rs=0;
            }
            r1=insert(r1,now);
        }
        root=merge(r1,r4);
    }
    down(root);
    for(int i=1;i<=m;i++)
        printf("%d ",cnt[i]);
    return 0;
}

可持久性treap模板：

洛谷P3835

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
using namespace std;

const int maxn=5e5+4;
int n;

struct node{
    int l,r,rand,val,siz;
}tree[40*maxn];	//保险吧，其实30*就够
int rt[maxn];

struct pir{
    int first,second;
    pir(int _fi,int _se){
        first=_fi;
        second=_se;
    }
};


int new_node(int val=0){
    static int cnt;
    cnt++;
    tree[cnt].val=val;
    tree[cnt].rand=rand();
    tree[cnt].siz=1;
    return cnt;
}

int cpy_node(int src){
    int now=new_node();
    tree[now]=tree[src];
    return now;
}

void pushup(int o){
    tree[o].siz=tree[tree[o].l].siz+tree[tree[o].r].siz+1;
}

pir split(int k,int val){   //<=val的为第一棵树，>val的在第二棵树中
    pir res(0,0);
    if(!k)
        return res;
    int now=cpy_node(k);
    if(val<tree[k].val){
        res=split(tree[k].l,val);
        tree[now].l=res.second;
        res.second=now;
    }
    else{
        res=split(tree[k].r,val);
        tree[now].r=res.first;
        res.first=now;
    }
    pushup(now);
    return res;
}

int merge(int x,int y){ //按参数传递顺序保证有序性
    if(x==0 || y==0)
        return x+y;
    if(tree[x].rand<tree[y].rand){
        tree[x].r=merge(tree[x].r,y);
        pushup(x);
        return x;
    }
    else{
        tree[y].l=merge(x,tree[y].l);
        pushup(y);
        return y;
    }
}

void insert(int pre,int now,int val){   //pre是在哪个版本上操作
    pir tmp=split(rt[pre],val);
    rt[now]=merge(tmp.first,merge(new_node(val),tmp.second));
}

//对着别人的模板实现的时候，两次错误都出在这里
void del(int pre,int now,int val){
    pir l=split(rt[pre],val-1);
    pir r=split(l.second,val);
    r.first=merge(tree[r.first].l,tree[r.first].r); //对于可能有多个val的情况，这一步使得只去掉一个val
    rt[now]=merge(l.first,merge(r.first,r.second));
}

int v2r(int pre,int now,int val){   //val to rank
    pir rt1=split(rt[pre],val-1);
    int res=tree[rt1.first].siz;//由于有-INF，不再+1
    rt[now]=merge(rt1.first,rt1.second);
    return res;
}

int r2v(int now,int rnk){
    int k=now;
    while(rnk<=tree[tree[k].l].siz||rnk>tree[tree[k].l].siz+1){
        if(rnk<=tree[tree[k].l].siz)
            k=tree[k].l;
        else{
            rnk-=(tree[tree[k].l].siz+1);
            k=tree[k].r;
        }
    }
    return tree[k].val;
}

int r2v(int pre,int now,int rnk){
    rt[now]=rt[pre];
    return r2v(rt[now],rnk+1);  //考虑到插入的-INF
}

int pred(int pre,int now,int val){	//比val小的上一个元素
    pir rt1=split(rt[pre],val-1);
    int res=r2v(rt1.first,tree[rt1.first].siz);
    rt[now]=merge(rt1.first,rt1.second);
    return res;
}

int succ(int pre,int now,int val){	//比val大的下一个元素
    pir rt1=split(rt[pre],val);
    int res=r2v(rt1.second,1);
    rt[now]=merge(rt1.first,rt1.second);
    return res;
}

int main(){
    srand(time(0));
    insert(0,0,-2147473647);
    insert(0,0,2147483647);
    cin>>n;
    for(int i=1;i<=n;i++){
        int v,opt,x;
        cin>>v>>opt>>x;
        if(opt==1){
            insert(v,i,x);
        }else if(opt==2){
            del(v,i,x);
        }else if(opt==3){
            cout<<v2r(v,i,x)<<endl;
        }else if(opt==4){
            cout<<r2v(v,i,x)<<endl;
        }else if(opt==5){
            cout<<pred(v,i,x)<<endl;
        }else{
            cout<<succ(v,i,x)<<endl;
        }
    }
    return 0;
}