平衡树比较与应用

发表于 | 分类于 | 阅读次数:

各种平衡树比较
| 平衡树 | 附加域 | 平衡性 | 效率 | 编程难度 | 实用性 | 特点 |
| :—: | :–: | :——: | :——: | :–: | :–: | :–: |
| Treap | 修正值 | 较好 | 较快 | 易 | 好 | 随机平衡 |
| Splay | - | 玄学（均摊 中） | 玄学（均摊 中） | 中 | 好 | 灵活易变 |
| SBT | 子树大小 | 好 | 快 | 中 | 好 | 短小精悍 |
| BST | 无 | 差 | 不稳定 | 易 | 一般 | 编写容易 |
##1 Splay Tree
###1.1 模板
关于写法：

我之前写的是仿照维基百科标程用数组模拟链表写的，其优点是方便初学者理解（当时要给小伙伴们讲课嘛），但是其相当冗长，考试时缺少优势。

我这里写的是简写的非递归版，综合各方面优点，既简短又方便调试。

当然网上还有大神写的递归版，个人认为调试不便。
####1.1.1 普通平衡树

维护一些数，其中需要提供以下操作：

1. 插入 x x x 数；
2. 删除 x x x 数（若有多个相同的数，因只删除一个）；
3. 查询 x x x 数的排名（若有多个相同的数，因输出最小的排名）；
4. 查询排名为 x x x 的数；
5. 求 x x x 的前趋（前趋定义为小于 x x x，且最大的数）；
6. 求 x x x 的后继（后继定义为大于 x x x，且最小的数）。

注意：本代码中如果找不到 lowerBound 或 upperBound 会返回 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
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN=(int)1e5+5,INF=~0U>>1;

int n;

class SPT
{
    private:
        struct N
        {
            int val;
            int fa,c[2];
            int num,size;//出现次数
        } t[MAXN];
        int size,tcnt;//节点个数，已使用的数组元素个数
        int root;
        
        void update(int x)
        {t[x].size=t[t[x].c[0]].size+t[t[x].c[1]].size+t[x].num;}
        
		bool iden(int x)//lc:0 rc:1
        {return t[t[x].fa].c[0]!=x;}
        
		void cnn(int x,int fa,bool son)
        {
            if(x) t[x].fa=fa;
            if(fa) t[fa].c[son]=x;
            else root=x;
        }
        void rot(int x)
        {
            int y=t[x].fa,z=t[y].fa;
            bool xType=iden(x),yType=iden(y);
            cnn(t[x].c[!xType],y,xType);
            cnn(y,x,!xType);
            cnn(x,z,yType);
            update(y);update(x);
        }
        void splay(int x,int toFa)
        {
            while(t[x].fa!=toFa)
            {
                int xFa=t[x].fa;
                if(t[xFa].fa==toFa) rot(x);
                else
                {
                    if(iden(xFa)==iden(x)) {rot(xFa);rot(x);}
                    else {rot(x);rot(x);}
                }
            }
        }
        int find(int val)
        {
            int x=root;
            while(x)
            {
                if(val==t[x].val) return x;
                if(val<t[x].val) x=t[x].c[0];
                else x=t[x].c[1];
            }
            return 0;
        }
        int stMin(int x)
        {
            int y=0;
            while(x){y=x;x=t[x].c[0];}
            return y;
        }
        int stMax(int x)
        {
            int y=0;
            while(x){y=x;x=t[x].c[1];}
            return y;
        }
    public:
        void insert(int val)
        {
            ++size;
            int x=root,y=0;
            while(x)
            {
                y=x;
                if(val==t[x].val)
                {
                    ++t[x].num;
                    splay(x,0);
                    return;
                }
                if(val<t[x].val) x=t[x].c[0];
                else x=t[x].c[1];
            }
            x=++tcnt;
            t[x].val=val,t[x].fa=y;
            t[x].num=t[x].size=1; 
            cnn(x,y,val>t[y].val);
            splay(x,0);
        }
        void erase(int val)
        {
            --size;
            int x=find(val);
            if(!x) return;
            if(t[x].num>1)
            {
                --t[x].num;
                splay(x,0);
                return;
            }
            splay(x,0);
            int y=stMax(t[x].c[0]),z=stMin(t[x].c[1]);
            if((!y)&&(!z)) root=0,size=0;
            else if(!y)
            {
                splay(z,0);
                t[z].c[0]=0;
                update(z);
            }else if(!z)
            {
                splay(y,0);
                t[y].c[1]=0;
                update(y);
            }else
            {
                splay(y,0);splay(z,y);
                t[z].c[0]=0;
                update(z);update(y);
            }
        }
        int lower(int val)
        {
            int x=root,y=0;
            while(x)
            {
                if(t[x].val<val) y=x,x=t[x].c[1];
                else x=t[x].c[0];
            }
            return t[y].val;
        }
        int upper(int val)
        {
            int x=root,y=0;
            while(x)
            {
                if(t[x].val>val) y=x,x=t[x].c[0];
                else x=t[x].c[1];
            }
            return t[y].val;
        }
        int n2r(int val)
        {
            insert(val);
            int res=t[t[root].c[0]].size+1;
            erase(val);
            return res;
        }
        int r2n(int rank)
        {
            int x=root;
            while(rank<=t[t[x].c[0]].size||rank>t[t[x].c[0]].size+t[x].num)
            {
                if(rank<=t[t[x].c[0]].size)
                    x=t[x].c[0];
                else rank-=t[t[x].c[0]].size+t[x].num,x=t[x].c[1];
            }
            return t[x].val;
        }
} spt;
int main()
{
	freopen("splay.in","r",stdin); 
    scanf("%d",&n);
    while(n--)
    {
        int opt,x;scanf("%d%d",&opt,&x);
        if(opt==1) spt.insert(x);
        else if(opt==2) spt.erase(x);
        else if(opt==3) printf("%d\n",spt.n2r(x));
        else if(opt==4) printf("%d\n",spt.r2n(x));
        else if(opt==5) printf("%d\n",spt.lower(x));
        else if(opt==6) printf("%d\n",spt.upper(x));
    }
    return 0; 
}

####1.1.2 文艺平衡树
区间翻转

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
#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN=100005;

int n,m;

void swap(int & a,int & b)
{int t=a;a=b;b=t;}

class SPT
{
    public:
    int root,size;
    private:
    struct N
    {
        int fa,c[2];
        int size;
        int val;
        bool tag;
    }t[MAXN];
    void update(int x)
    {t[x].size=t[t[x].c[0]].size+t[t[x].c[1]].size+1;}
    void cnn(int x,int fa,int cType)
    {
        if(x) t[x].fa=fa;
        if(fa) t[fa].c[cType]=x;
        else root=x;
    }
    bool iden(int x)
    {return t[t[x].fa].c[0]!=x;}
    void pushDown(int x)
    {
        if(t[x].tag)
        {
            swap(t[x].c[0],t[x].c[1]);
            t[t[x].c[0]].tag^=1,t[t[x].c[1]].tag^=1;
            t[x].tag=0;
        }
    }
    void rot(int x)
    {
        int y=t[x].fa,z=t[y].fa;
        bool xType=iden(x),yType=iden(y);
        cnn(t[x].c[!xType],y,xType);
        cnn(y,x,!xType);
        cnn(x,z,yType);
        update(y);update(x);
    }
    void splay(int x,int toFa)
    {
        while(t[x].fa!=toFa)
        {
            int xFa=t[x].fa;
            if(t[xFa].fa==toFa) rot(x);
            else if(iden(x)==iden(xFa))
                rot(xFa),rot(x);
            else rot(x),rot(x);
        }
    }
    int r2i(int rank)
    {
        int x=root;pushDown(x);
        while(rank!=t[t[x].c[0]].size+1)
        {
            if(rank<t[t[x].c[0]].size+1)
                x=t[x].c[0];
            else rank-=t[t[x].c[0]].size+1,x=t[x].c[1];
            pushDown(x);
        }
        return x;
    }
    public:
    int build(int l,int r)
    {
        if(l>r) return 0;
        int x=(l+r)>>1;
        cnn(build(l,x-1),x,0);
        cnn(build(x+1,r),x,1);
        ++size;
        t[x].val=x-1;
        update(x);
        return x;
    }
    void print(int x)
    {
        if(!x) return;
        pushDown(x);
        print(t[x].c[0]);
        if(x!=1&&x!=n+2) printf("%d ",t[x].val);
        print(t[x].c[1]);
    }
    void work(int l,int r)
    {
        int p1=r2i(l),p2=r2i(r+2);
        splay(p1,0),splay(p2,root);
        t[t[p2].c[0]].tag^=1;
    }
    int getRt(){return root;}
} spt;

int main()
{
    scanf("%d%d",&n,&m);
    spt.root=spt.build(1,n+2);
    while(m--)
    {
        int l,r;scanf("%d%d",&l,&r);
        spt.work(l,r);
    }
    spt.print(spt.getRt());
	return 0;
}

###1.2 题目
####1.2.1 HNOI2004 宠物收养所

最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值 a （ a 是一个正整数， a<$2^{31}$ ），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。 

1. 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为 a ，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为 a-b 和 a+b ，那么领养者将会领养特点值为 a-b 的那只宠物。
2. 收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为 a ，存在两个领养者他们希望领养宠物的特点值分别为 a-b 和 a+b ，那么特点值为 a-b 的那个领养者将成功领养该宠物。

一个领养者领养了一个特点值为 a 的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为 abs(a-b) 。

你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。
求不满意度之和

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
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<iostream>
#include<cstdio>
#define x node[x_p]
#define y node[y_p]
#define z node[z_p]
#define u node[u_p]
#define v node[v_p]
#define p node[p_p]
using namespace std;
 
const int MAXN=80000,INF=~0U>>1,P=1000000;
 
struct splayTree
{
    int root,size;
	int type;
    struct N
    {
        int lc,rc,fa;
        int val;
        N(){lc=rc=fa=val=0;}
    }node[MAXN+1];int ncnt;
    void lRotate(int x_p)
    {
        int y_p=x.rc;
        x.rc=y.lc;
        if(y.lc) node[y.lc].fa=x_p;
        y.fa=x.fa;
        if(!x.fa) root=y_p;
        else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
        else node[x.fa].rc=y_p;
        y.lc=x_p,x.fa=y_p;
    }
    void rRotate(int x_p)
    {
        int y_p=x.lc;
        x.lc=y.rc;
        if(y.rc) node[y.rc].fa=x_p;
        y.fa=x.fa;
        if(!x.fa) root=y_p;
        else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
        else node[x.fa].rc=y_p;
        y.rc=x_p,x.fa=y_p;
    }
    void splay(int x_p)
    {
        while(x.fa)
        {
            if(!node[x.fa].fa)
            {
                if(node[x.fa].lc==x_p) rRotate(x.fa);
                else lRotate(x.fa);
            }else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].lc==x.fa)
            {
                rRotate(node[x.fa].fa);
                rRotate(x.fa);
            }else if(node[x.fa].rc==x_p&&node[node[x.fa].fa].rc==x.fa)
            {
                lRotate(node[x.fa].fa);
                lRotate(x.fa);
            }else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].rc==x.fa)
            {
                rRotate(x.fa);
                lRotate(x.fa);
            }else
            {
                lRotate(x.fa);
                rRotate(x.fa);
            }
        }
    }
    void replace(int u_p,int v_p)
    {
        if(!u.fa) root=v_p;
        else if(u_p==node[u.fa].lc) node[u.fa].lc=v_p;
        else node[u.fa].rc=v_p;
        if(v_p) v.fa=u.fa;
    }
    int subtreeMin(int u_p)
    {
        while(u.lc) u_p=u.lc;
        return u_p;
    }
    splayTree(){root=size=ncnt=type=0;}
    void insert(int val)
    {
        int z_p=root;
        int p_p=0;
        while(z_p)
        {
            p_p=z_p;
            if(node[z_p].val<val) z_p=node[z_p].rc;
            else z_p=node[z_p].lc;
        }
        z_p=++ncnt;
        z.val=val;
        z.fa=p_p;
        if(!p_p) root=z_p;
        else if(p.val<z.val) p.rc=z_p;
        else p.lc=z_p;
        splay(z_p);
        ++size;
    }
    void erase(int z_p)
    {
        splay(z_p);
        if(!z.lc) replace(z_p,z.rc);
        else if(!z.rc) replace(z_p,z.lc);
        else
        {
            int y_p=subtreeMin(z.rc);
            if(y.fa!=z_p)
            {
                replace(y_p,y.rc);
                y.rc=z.rc;
                node[y.rc].fa=y_p;
            }
            replace(z_p,y_p);   
            y.lc=z.lc;
            node[y.lc].fa=y_p;
        }
        --size;
    }
    int work(int val,int rtype)
    {
        if(!size) {type=rtype;insert(val);return 0;}
		if(rtype==type) {insert(val);return 0;}
        int x_p=-1,y_p=-1,u_p=root;
        while(u_p)
        	if(u.val<=val)
        	{
        		x_p=u_p;
        		u_p=u.rc;
        	}else u_p=u.lc;
        u_p=root;
        while(u_p)
        	if(u.val>=val)
        	{
        		y_p=u_p;
        		u_p=u.lc;
        	}else u_p=u.rc;
        if(x_p==-1) x_p=y_p;
        else if(y_p!=-1)
			if(y.val-val<val-x.val) x_p=y_p;
        erase(x_p);
        return x.val>val?x.val-val:val-x.val;
    }
} spT;

int main()
{ 
    int i;int n;int ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        int rtype,val;
        scanf("%d%d",&rtype,&val);
        ans=(ans+spT.work(val,rtype))%P;
    }
    printf("%d\n",ans);
    return 0;
}

####1.2.2 [HNOI2002] 营业额统计

Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况： 该天的最小波动值。

当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。 第一天的最小波动值为第一天的营业额。

天数 $n\leq32767$，每天的营业额 $a_i\leq10^6$

最后结果 $T<=2^{31}$

这道题纯属是练手的，对这道题不必想如何统计前面树中的最小值，因为此题是要每个数都要插入的，插入完之后此节点一定是根节点，那么只要取右子树中的最小值和左子树中的最大值与此节点的差值即可。最难的删除操作在此题也不涉及。

唯一的不同点就是这道题的数据不保证没有重复，所以插入的时候如果发现此数值已经在树中就不必插入了。

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
#include<iostream>
#include<cstdio>
#define x node[x_p]
#define y node[y_p]
#define z node[z_p]
#define p node[p_p]
#define u node[u_p]
#define v node[v_p]
#define min(a,b) (a<b?a:b)
using namespace std;

const int MAXN=32767,INF=~0U>>1;

struct splayTree
{
	int root,size;
	struct N
	{
		int lc,rc,fa;
		int val;
		N(){lc=rc=fa=val=0;}
	}node[MAXN+10];int ncnt;
	void lRotate(int x_p)
	{
		int y_p=x.rc;
		x.rc=y.lc;
		if(y.lc) node[y.lc].fa=x_p;
		y.fa=x.fa;
		if(!x.fa) root=y_p;
		else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
		else node[x.fa].rc=y_p;
		y.lc=x_p,x.fa=y_p;
	}
	void rRotate(int x_p)
	{
		int y_p=x.lc;
		x.lc=y.rc;
		if(y.rc) node[y.rc].fa=x_p;
		y.fa=x.fa;
		if(!x.fa) root=y_p;
		else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
		else node[x.fa].rc=y_p;
		y.rc=x_p,x.fa=y_p;
	}
	void splay(int x_p)
	{
		while(x.fa)
		{
			if(!node[x.fa].fa)
			{
				if(node[x.fa].lc==x_p) rRotate(x.fa);
				else lRotate(x.fa);
			}else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].lc==x.fa)
			{
				rRotate(node[x.fa].fa);
				rRotate(x.fa);
			}else if(node[x.fa].rc==x_p&&node[node[x.fa].fa].rc==x.fa)
			{
				lRotate(node[x.fa].fa);
				lRotate(x.fa);
			}else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].rc==x.fa)
			{
				rRotate(x.fa);
				lRotate(x.fa);
			}else
			{
				lRotate(x.fa);
				rRotate(x.fa);
			}
		}
	}
	int subtreeMin(int u_p)
	{
		while(u.lc) u_p=u.lc;
		return u_p;
	}
	int subtreeMax(int u_p)
	{
		while(u.rc) u_p=u.rc;
		return u_p;
	}
	splayTree(){root=0,size=0,ncnt=0;}
	int insert(int val)
	{
		int z_p=root;
		int p_p=0;
		while(z_p)
		{
			p_p=z_p;
			if(z.val==val) return 1;
			if(z.val<val) z_p=node[z_p].rc;
			else z_p=node[z_p].lc;
		}
		z_p=++ncnt;
		z.val=val;
		z.fa=p_p;
		if(!p_p) root=z_p;
		else if(p.val<z.val) p.rc=z_p;
		else p.lc=z_p;
		splay(z_p);
		++size;
		return 0;
	}
	int work(int val)
	{
		if(insert(val)) return 0;
		if(size==1) return val;
		int tmp=subtreeMin(node[root].rc);
		if(!node[root].lc)
			return node[subtreeMin(node[root].rc)].val-val;
		if(!node[root].rc)
			return val-node[subtreeMax(node[root].lc)].val;
		return min(node[subtreeMin(node[root].rc)].val-val,
				val-node[subtreeMax(node[root].lc)].val);
	}
} spT;

int main()
{
	int i;
	int n;
	int ans=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		int rn;scanf("%d",&rn);
		ans+=spT.work(rn);
	}
	printf("%d\n",ans);
	return 0;
}

##2 Treap
###2.1 模板
注意：本代码中如果找不到 lowerBound 或 upperBound 会返回 0 ，具体使用时要根据需要更改。
####2.1.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
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <cstdio>
#include <cstdlib>
using namespace std;

const int MAXN=100005;


class TREAP
{
	private:
        struct N
        {
            int val;
            int fa,c[2];
            int num,sz;//出现次数
            int w;
        } t[MAXN];
		int sz,tcnt;int rt;

		void upd(int x)
		{t[x].sz=t[t[x].c[0]].sz+t[t[x].c[1]].sz+t[x].num;}
		void pushup(int x)
		{while(x){upd(x);x=t[x].fa;}}

		bool iden(int x)//lc:0 rc:1
        {return t[t[x].fa].c[0]!=x;}
        
        void cnn(int x,int fa,bool son)
        {
            if(x) t[x].fa=fa;
            if(fa) t[fa].c[son]=x;
            else rt=x;
        }
        void rot(int x)
        {
            int y=t[x].fa,z=t[y].fa;
            bool xType=iden(x),yType=iden(y);
            cnn(t[x].c[!xType],y,xType);
            cnn(y,x,!xType);
            cnn(x,z,yType);
            upd(y);upd(x);
        }
		int find(int val)
		{
			int x=rt;
			while(x)
			{
				if(t[x].val==val) return x;
				x=t[x].c[val>t[x].val];
			}
			return 0;
		}
		int stLim(int x,bool type)
		{
			int y=0;
			while(x)
			{
				y=x;
				x=t[x].c[type];
			}
			return y;
		}
	public:
		void insert(int val)
		{
			++sz;
			int x=rt,y=0;
			while(x)
			{
				if(val==t[x].val)
				{
					++t[x].num;
					pushup(x);
					return;
				}
				y=x;
				x=t[x].c[val>t[x].val];
			}
			x=++tcnt;
			t[x].num=t[x].sz=1;
			t[x].val=val;
			t[x].w=rand();
			if(y)
			{
				t[x].fa=y;
				t[y].c[val>t[y].val]=x;
				while(t[x].w<t[t[x].fa].w) rot(x);
				pushup(x);
			}
			else rt=x;
		}
		void erase(int val)
		{
			int x=find(val);
			if(!x) return;
			if(t[x].num>1)
			{
				--t[x].num;
				pushup(x);
				return;
			}
			while(t[x].c[0]||t[x].c[1])
			{
				if(t[x].c[0]&&t[x].c[1])
					rot(t[x].c[t[t[x].c[1]].w<t[t[x].c[0]].w]);
				else rot(t[x].c[0]|t[x].c[1]);
			}
			t[t[x].fa].c[t[t[x].fa].c[1]==x]=0;
			pushup(x);
			if(--sz==0) rt=0;
		}
		int lower(int val)
		{
			int x=rt,y=0;
			while(x)
			{
				if(t[x].val<val)
					y=x,x=t[x].c[1];
				else x=t[x].c[0];
			}
			return t[y].val;
		}
		int upper(int val)
		{
			int x=rt,y=0;
			while(x)
			{
				if(t[x].val>val)
					y=x,x=t[x].c[0];
				else x=t[x].c[1];
			}
			return t[y].val;
		}
		int n2r(int val)
		{
			int x=rt,res=1;
			while(x)
			{
				if(t[x].val<val)
				{
					res+=t[t[x].c[0]].sz+t[x].num;
					x=t[x].c[1];
				}
				else x=t[x].c[0];
			}
			return res;
		}
		int r2n(int k)
		{
			int x=rt;
			while(k<=t[t[x].c[0]].sz||t[t[x].c[0]].sz+t[x].num<k)
			{
				if(k<=t[t[x].c[0]].sz)
					x=t[x].c[0];
				else
				{
					k-=t[t[x].c[0]].sz+t[x].num;
					x=t[x].c[1];
				}
			}
			return t[x].val;
		}
} treap;

int main()
{
    int n;scanf("%d",&n);
    while(n--)
    {
        int opt,x;scanf("%d%d",&opt,&x);
        if(opt==1) treap.insert(x);
        else if(opt==2) treap.erase(x);
        else if(opt==3) printf("%d\n",treap.n2r(x));
        else if(opt==4) printf("%d\n",treap.r2n(x));
        else if(opt==5) printf("%d\n",treap.lower(x));
        else if(opt==6) printf("%d\n",treap.upper(x));
    }
    return 0; 
}

####2.1.2 二逼平衡树

维护一个有序数列，其中需要提供以下操作：

1. 查询 x x x 在区间内的排名；
2. 查询区间内排名为 k k k 的值；
3. 修改某一位置上的数值；
4. 查询 x x x 在区间内的前趋（前趋定义为小于 x x x，且最大的数）；
5. 查询 x x x 在区间内的后继（后继定义为大于 x x x，且最小的数）。

由于要操作区间，考虑在平衡树外套线段树，由于 splay 易被卡然后 TLE，这里用 Treap。

树套树中的一大难点就是分配内存问题。首先，应注意到如果将 Treap 完全封装到 class 里面的话会 MLE ，正确的做法是统一分配 Treap 节点；然后，整个线段树上每个节点都有的 Treap 一共有 $Nlog_2N$ 个节点，而我们删除一个 Treap 中的节点并未在内存中删除，所以我们对于每次更改操作需要 $log_2N$ 个节点，这又是 $Nlog_2N$ 个，一共需要 $2Nlog_2N$ 个 Treap 节点，所以需要开 $1.5*10^6$ 左右我就是因为这个 RE 了。

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;

const int MAXN=50005,INF=~0U>>1;

struct N
{
	int val;
    int fa,c[2];
    int num,sz;//出现次数
    int w;
} tp[MAXN];int tpcnt;
#define t tp
#define tcnt tpcnt
class TREAP
{
	private:
		int sz,rt;
		void upd(int x)
		{t[x].sz=t[t[x].c[0]].sz+t[t[x].c[1]].sz+t[x].num;}
		void pushup(int x)
		{while(x){upd(x);x=t[x].fa;}}

		bool iden(int x)//lc:0 rc:1
        {return t[t[x].fa].c[0]!=x;}
        
        void cnn(int x,int fa,bool son)
        {
            if(x) t[x].fa=fa;
            if(fa) t[fa].c[son]=x;
            else rt=x;
        }
        void rot(int x)
        {
            int y=t[x].fa,z=t[y].fa;
            bool xType=iden(x),yType=iden(y);
            cnn(t[x].c[!xType],y,xType);
            cnn(y,x,!xType);
            cnn(x,z,yType);
            upd(y);upd(x);
        }
		int find(int val)
		{
			int x=rt;
			while(x)
			{
				if(t[x].val==val) return x;
				x=t[x].c[val>t[x].val];
			}
			return 0;
		}
		int stLim(int x,bool type)
		{
			int y=0;
			while(x)
			{
				y=x;
				x=t[x].c[type];
			}
			return y;
		}
	public:
		void insert(int val)
		{
			++sz;
			int x=rt,y=0;
			while(x)
			{
				if(val==t[x].val)
				{
					++t[x].num;
					pushup(x);
					return;
				}
				y=x;
				x=t[x].c[val>t[x].val];
			}
			x=++tcnt;
			t[x].num=t[x].sz=1;
			t[x].val=val;
			t[x].w=rand();
			if(y)
			{
				t[x].fa=y;
				t[y].c[val>t[y].val]=x;
				while(t[x].w<t[t[x].fa].w) rot(x);
				pushup(x);
			}
			else rt=x;
		}
		void erase(int val)
		{
			int x=find(val);
			if(!x) return;
			if(t[x].num>1)
			{
				--t[x].num;
				pushup(x);
				return;
			}
			while(t[x].c[0]||t[x].c[1])
			{
				if(t[x].c[0]&&t[x].c[1])
					rot(t[x].c[t[t[x].c[1]].w<t[t[x].c[0]].w]);
				else rot(t[x].c[0]|t[x].c[1]);
			}
			t[t[x].fa].c[t[t[x].fa].c[1]==x]=0;
			pushup(x);
			if(--sz==0) rt=0;
		}
		int lower(int val)
		{
			int x=rt,y=0;
			while(x)
			{
				if(t[x].val<val)
					y=x,x=t[x].c[1];
				else x=t[x].c[0];
			}
			return t[y].val;
		}
		int upper(int val)
		{
			int x=rt,y=0;
			while(x)
			{
				if(t[x].val>val)
					y=x,x=t[x].c[0];
				else x=t[x].c[1];
			}
			return t[y].val;
		}
		int n2r(int val)
		{
			int x=rt,res=1;
			while(x)
			{
				if(t[x].val<val)
				{
					res+=t[t[x].c[0]].sz+t[x].num;
					x=t[x].c[1];
				}
				else x=t[x].c[0];
			}
			return res;
		}
		int r2n(int k)
		{
			int x=rt;
			while(k<=t[t[x].c[0]].sz||t[t[x].c[0]].sz+t[x].num<k)
			{
				if(k<=t[t[x].c[0]].sz)
					x=t[x].c[0];
				else
				{
					k-=t[t[x].c[0]].sz+t[x].num;
					x=t[x].c[1];
				}
			}
			return t[x].val;
		}
};
#undef t
#undef tcnt
int na[MAXN];
struct SEGTN
{
	int l,r,lc,rc;
	TREAP dat;
} t[MAXN];int tcnt=1;const int rt=1;
void buildSEGT(int o,int l,int r)
{
	t[o].l=l,t[o].r=r;
	for(int i=l;i<=r;i++) t[o].dat.insert(na[i]);	
	if(l==r) return;
	int mid=(l+r)>>1;
	t[o].lc=++tcnt;buildSEGT(t[o].lc,l,mid);
	t[o].rc=++tcnt;buildSEGT(t[o].rc,mid+1,r);
}
int calLowNum(int o,int l,int r,int val)
{
	if(l<=t[o].l&&t[o].r<=r) return t[o].dat.n2r(val)-1;
	int mid=(t[o].l+t[o].r)>>1;
	int res=0;
	if(l<=mid) res+=calLowNum(t[o].lc,l,r,val);
	if(r>mid) res+=calLowNum(t[o].rc,l,r,val);
	return res;
}
int getNbyR(int l,int r,int val)
{return calLowNum(rt,l,r,val)+1;}
int getRbyN(int l,int r,int rk)
{
	int L=0,R=(int)1e8,tmpRk,mid;
	while(L<=R)
	{
		mid=(L+R)>>1;
		tmpRk=calLowNum(rt,l,r,mid)+1;
		if(tmpRk==rk) return mid;
		if(tmpRk>rk) R=mid-1;
		else L=mid+1;
	}
}
void chCh(int o,int	pos,int val)
{
	if(t[o].l<=pos&&pos<=t[o].r)
	{
		t[o].dat.erase(na[pos]);
		t[o].dat.insert(val);
		na[pos]=val;return;
	}
	t[o].dat.erase(na[pos]);
	t[o].dat.insert(val);
	int mid=(t[o].l+t[o].r)>>1;
	if(pos<=mid) chCh(t[o].lc,pos,val);
	else if(pos>mid) chCh(t[o].rc,pos,val);
}
int calLower(int o,int l,int r,int val)
{
	if(l<=t[o].l&&t[o].r<=r) return t[o].dat.lower(val);
	int mid=(t[o].l+t[o].r)>>1;
	int res1=-INF,res2=-INF;
	if(l<=mid) res1=calLower(t[o].lc,l,mid,val);
	if(r>mid) res2=calLower(t[o].lc,mid+1,r,val);
	return max(res1,res2);
}
int calUpper(int o,int l,int r,int val)
{
	if(l<=t[o].l&&t[o].r<=r) return t[o].dat.upper(val);
	int mid=(t[o].l+t[o].r)>>1;
	int res1=INF,res2=INF;
	if(l<=mid) res1=calUpper(t[o].lc,l,mid,val);
	if(r>mid) res2=calUpper(t[o].rc,mid+1,r,val);
	return min(res1,res2);
}
int main()
{
    int i,n,m;scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) scanf("%d",&na[i]);
    while(m--)
    {
        int opt,l,r,pos,x;scanf("%d%d",&opt);
        if(opt==3) scanf("%d%d",&pos,&x);
		else scanf("%d%d%d",&l,&r,&x);
		if(opt==1) printf("%d\n",getRbyN(l,r,x));
		else if(opt==2) printf("%d\n",getNbyR(l,r,x));
		else if(opt==3) chCh(rt,pos,x);
		else if(opt==4) printf("%d\n",calLower(rt,l,r,x));
		else if(opt==5) printf("%d\n",calUpper(rt,l,r,x));
    }
    return 0; 
}