平衡树被虐笔记

字数统计: 2.3k字 | 阅读时长: 13分

RT，博主最近学习了平衡树splay，写题根本调不出来，被吊打了。

板子：普通平衡树

传送门

平衡树基本操作，这里不想写教学，挂个链接好了：yyb的教学

贴板子：

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
#include<cstdio>
#include<iostream>
using namespace std;
struct tree{
    int cnt,ch[2],val,fa,sum;
}t[100001];
int root,n,cnt;
inline void pushup(int x){
    t[x].sum=t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].cnt;
}
inline void rotate(int x){ //向上旋转x
    int y=t[x].fa,z=t[y].fa,f1=(t[y].ch[1]==x),f2=(t[z].ch[1]==y);
    t[z].ch[f2]=x; t[x].fa=z;
    t[y].ch[f1]=t[x].ch[f1^1]; t[t[x].ch[f1^1]].fa=y;
    t[x].ch[f1^1]=y; t[y].fa=x;
    pushup(y),pushup(x);
}
inline void splay(int x,int goal){ //使x成为goal的孩子
    int y,z;
    while (t[x].fa!=goal){
        y=t[x].fa,z=t[y].fa;
        if (z!=goal)
            if ((t[y].ch[0]==x)^(t[z].ch[0]==y)) rotate(y); else rotate(x);
        rotate(x);
    }
    if (!goal) root=x;
}
inline void insert(int x){ //插入x
    int y=root,f=0;
    while (y&&t[y].val!=x)
        f=y,y=t[y].ch[x>t[y].val];
    if (y) t[y].cnt++;
    else{
        y=++cnt;
        if (f) t[f].ch[x>t[f].val]=y;
        t[cnt].val=x; t[cnt].fa=f;
        t[cnt].cnt=1; t[cnt].sum=1;
        t[y].ch[0]=t[y].ch[1]=0;
    }
    splay(y,0);
}
inline void find(int x){ //查找x的位置并使它成为根
    if (!root) return;
    int y=root;
    while (t[y].ch[x>t[y].val]&&x!=t[y].val) y=t[y].ch[x>t[y].val];
    splay(y,0);
}
inline int nex(int x,int f){ //查找x的前驱后继
    find(x); int y=root;
    if (t[y].val>x&&f) return y;
    if (t[y].val<x&&!f) return y;
    y=t[y].ch[f];
    while (t[y].ch[f^1]) y=t[y].ch[f^1];
    splay(y,0);
    return y;
}
inline void del(int x){ //delete x
    int head=nex(x,0),tail=nex(x,1);
    splay(head,0); splay(tail,head);
    int y=t[tail].ch[0];
    if (t[y].cnt>1){
        t[y].cnt--; //t[head].sum--; t[y].sum--;
        splay(y,0);
    }
    else t[tail].ch[0]=0;
}
inline int query(int x){
    find(x); return t[t[root].ch[0]].sum;
}
inline int atrank(int x){	//查找第k大
    int y=root;
    if (t[y].sum<x) return 0;
    while (1){
        int z=t[t[y].ch[0]].sum+t[y].cnt;
        if (x>z) y=t[y].ch[1],x-=z;
        else{
            if (t[t[y].ch[0]].sum>=x) y=t[y].ch[0];
            else{
                splay(y,0);
                return t[y].val;
            }
        }
    }
}
int main(){
    //freopen("a.out","w",stdout);
    int opt,x; insert(2e9); insert(-2e9);
    scanf("%d",&n);
    while (n--){
        scanf("%d%d",&opt,&x);
        if (opt==1)	insert(x);
        if (opt==2) del(x);
        if (opt==3) printf("%d\n",query(x));
        if (opt==4) printf("%d\n",atrank(x+1));
        if (opt==5) printf("%d\n",t[nex(x,0)].val);
        if (opt==6) printf("%d\n",t[nex(x,1)].val);
        if (atrank(1)!=-2e9) insert(-2e9);
    }
    return 0;
}

[NOI2004]郁闷的出纳员

板子题调了好久。。。

简单说思路：A和S操作很少，直接暴力算，S时删除结点可以一个一个删也可以把小于x+min的数全部删了。由于最后一个问题我边删边记录不知道哪错了，所以直接记还剩下多少个和进来多少个做差了。

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
#include<cstdio>
#include<iostream>
using namespace std;
struct node{
    int sum,cnt,ch[2],fa,m;
}t[100001];
int n,minn,ans,root,cnt;
inline void pushup(int x){
    t[x].sum=t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].cnt;
}
inline void retate(int x){
    int y=t[x].fa,z=t[y].fa,f1=(t[y].ch[1]==x),f2=(t[z].ch[1]==y);
    t[z].ch[f2]=x; t[x].fa=z;
    t[y].ch[f1]=t[x].ch[f1^1]; t[t[x].ch[f1^1]].fa=y;
    t[x].ch[f1^1]=y; t[y].fa=x;
    pushup(y),pushup(x);
}
inline void splay(int x,int goal){
    int y,z;
    while (t[x].fa!=goal){
        y=t[x].fa,z=t[y].fa;
        if (z!=goal)
            if ((t[z].ch[1]==y)^(t[y].ch[1]==x)) retate(y); else retate(x);
        retate(x);
    }
    if (!goal) root=x;
}
inline void insert(int x){
    int y=root,f=0;
    while (y&&t[y].m!=x)
        f=y,y=t[y].ch[x>t[y].m];
    if (y) t[y].cnt++;
    else{
        y=++cnt;
        if (f) t[f].ch[x>t[f].m]=y;
        t[y].sum=1; t[y].cnt=1;
        t[y].fa=f; t[y].m=x;
        t[y].ch[0]=t[y].ch[1]=0;
    }
    splay(y,0);
}
inline void find(int x){
    if (!root) return;
    int y=root;
    while (t[y].m!=x&&t[y].ch[x>t[y].m]) y=t[y].ch[x>t[y].m];
    splay(y,0);
}
inline int atrank(int x){
    int y=root,z;
    if (t[y].sum<x||x<=0) return -1;
    while (1){
        z=t[t[y].ch[0]].sum+t[y].cnt;
        if (x>z) x-=z,y=t[y].ch[1];
        else{
            if (t[t[y].ch[0]].sum>=x) y=t[y].ch[0];
            else{
                splay(y,0);
                return t[y].m;
            }
        }
    }
}
inline void del(int x){
    if (x>atrank(t[root].sum)){
        // ans+=t[root].sum;
        root=0; t[root].sum=0;
        return;
    }
    find(x);
    int y=root,z;
    if (t[y].m==x){
        t[y].sum-=t[t[y].ch[0]].sum;// ans+=t[t[y].ch[0]].sum;
        t[y].ch[0]=0;
        return;
    }
    if (t[y].m<x){
        z=t[y].ch[1];
        while (t[z].ch[0]) z=t[z].ch[0];
        splay(z,0); t[z].sum-=t[t[z].ch[0]].sum;
        // ans+=t[t[y].ch[0]].sum;
        t[z].ch[0]=0;
    }
    else{
        // z=t[x].ch[0];
        // while (t[z].ch[1]) z=t[z].ch[1];
        // splay(z,y); 
        t[y].sum-=t[t[y].ch[0]].sum;
        // ans+=t[t[y].ch[0]].sum;
        t[y].ch[0]=0;
    }
}
inline void inc(int x,int y){
//	if (t[y].m!=2e9&&t[y].m!=-2e9)
    t[y].m+=x;
    if (t[y].ch[0]) inc(x,t[y].ch[0]);
    if (t[y].ch[1]) inc(x,t[y].ch[1]);
}
inline void dec(int x,int y){
    t[y].m-=x;
    if (t[y].ch[0]) dec(x,t[y].ch[0]);
    if (t[y].ch[1]) dec(x,t[y].ch[1]);
//	if (t[y].m!=2e9&&t[y].m!=-2e9){
        // if (t[y].m-x<minn) ans++;
//	}
}
int main(){
    int x; char ch[2];
    // freopen("a.out","w",stdout);
//	insert(2e9); insert(-2e9);
    scanf("%d%d",&n,&minn);
    while (n--){
        scanf("%s",ch);
//		getchar(); ch=getchar(); getchar();
        scanf("%d",&x);
        if (ch[0]=='I') if (x>=minn) insert(x),ans++;
        if (ch[0]=='A') inc(x,root);
        if (ch[0]=='S'){
            // int y=t[root].sum;
            del(x+minn),dec(x,root);
            // ans+=y-t[root].sum;
        }
        if (ch[0]=='F') printf("%d\n",atrank(t[root].sum-x+1));
    }
    printf("%d\n",ans-t[root].sum);
    return 0;
}

【模板】文艺平衡树（Splay）（还有一些合并和拆分）

挂个链接：学长的blog

splay最有名的区间翻转操作来啦！！！

在区间翻转操作中，我们更看重的是splay作为旋转树的性质，可以在不打破平衡树性质的情况下随便反转。如果我们要反转区间$[l,r]$，我们只要让$[l,r]$内的数在一个子树中，且这个子树中只有$[l,r]$，然后反转它，这一步可以通过懒标记来实现。

同时，如果向普通平衡树那样写的话，随便翻转势必会导致破坏平衡树的性质，所以我们存入平衡树的点值应该是它的位置。就是类似线段树的存法。

具体做法：首先，把$l-1$旋转到根，此时$[l,r]$和$[r+1,n]$全部在左子树中。那么我们再把$r+1$旋转到左子树的根，这时根的左子树的右子树中就只有$[l,r]$了。

对于翻转$[l,r]$：交换它的左右儿子，给左右儿子打上lazy即可。

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
#include<cstdio>
#include<iostream>
using namespace std;
struct node{
    int sum,val,ch[2],fa,tag,cnt;
}t[100011];
int n,m,a[100011],root,cnt;
inline void pushup(int x){
    t[x].sum=t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].cnt;
}
inline void pushdown(int x){
    if (!t[x].tag) return;
    t[t[x].ch[0]].tag^=1; t[t[x].ch[1]].tag^=1;
    t[x].tag=0; swap(t[x].ch[0],t[x].ch[1]);
}
int build(int rt,int l,int r){
    if (l>r) return 0;
    cnt++; int y=cnt;
    int mid=(l+r)>>1;
    t[y].fa=rt; t[y].val=a[mid];
    t[y].sum=1; t[y].cnt=1;
//	if (l==r) return y;
    t[y].ch[0]=build(y,l,mid-1);
    t[y].ch[1]=build(y,mid+1,r);
    pushup(y); return y;
}
inline void retate(int x){
    if (x==root) return;
    int y=t[x].fa,z=t[y].fa,f1=(t[y].ch[1]==x),f2=(t[z].ch[1]==y);
    // pushdown(z)
    pushdown(y); pushdown(x);
    t[z].ch[f2]=x;t[x].fa=z; 
    t[y].ch[f1]=t[x].ch[f1^1]; t[t[x].ch[f1^1]].fa=y;
    t[x].ch[f1^1]=y ;t[y].fa=x;
    pushup(y),pushup(x);
}
inline void splay(int x,int goal){
    int y,z;
    while (t[x].fa!=goal){
        y=t[x].fa,z=t[y].fa;
        if (z!=goal)
            if ((t[z].ch[1]==y)^(t[y].ch[1]==x)) retate(y); else retate(x);
        retate(x);
    }
    if (!goal) root=x;
}
inline int atrank(int x){
    int y=root,z;
    // if (t[y].sum<x) return 0;
    while (1){
        pushdown(y);
        z=t[t[y].ch[0]].sum+t[y].cnt;
        // if (x<=t[t[y].ch[0]].sum) y=t[y].ch[0];
        // else{
        // 	x-=t[t[y].ch[0]].sum+1;
        // 	if (!x) return y;
        // 	y=t[y].ch[1];
        // }
        if (x>z) y=t[y].ch[1],x-=z;
        else{
            if (t[t[y].ch[0]].sum>=x) y=t[y].ch[0];
            else{
                splay(y,0);
                return y;
            }
        }
    }
}
inline void turn(int l,int r){
    l=atrank(l); r=atrank(r+2);
    splay(l,0); splay(r,l);
    pushdown(root);
    t[t[t[root].ch[1]].ch[0]].tag^=1;
}
inline void print(int x){
    pushdown(x);
    if (t[x].ch[0]) print(t[x].ch[0]);
    if (t[x].val!=-2e9&&t[x].val!=2e9) printf("%d ",t[x].val);
    if (t[x].ch[1]) print(t[x].ch[1]);
}
int main(){
    int x,y;
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++) a[i+1]=i;
    a[1]=-2e9; a[n+2]=2e9;
    root=build(0,1,n+2);
    while (m--){
        scanf("%d%d",&x,&y);
        // x++,y++;
        turn(x,y);
    }
    print(root);
    return 0;
}

本文标题:平衡树被虐笔记

文章作者:Taduro

发布时间:2019年01月15日 - 08时34分

最后更新:2019年01月16日 - 12时30分

原始链接:http://dftyem.github.io/2019/01/15/平衡树被虐笔记/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 板子：普通平衡树
  2. 2. [NOI2004]郁闷的出纳员
  3. 3. 【模板】文艺平衡树（Splay）（还有一些合并和拆分）
,
载入天数...载入时分秒... 字数统计：75.7k