lemonoil

OI__nothing is impossible

最强平衡树——Treap[以我的最弱战胜你的最强]

• 标签: 平衡树 treap

仆の最弱を以て，君の最强を打ち破る。！！——Treap

本人蒟蒻，在平衡树坑中深陷数年。为了早日逃离此天坑，特作此文。

什么是平衡树?度娘传送门 什么是treap？ACdreamers%%% 注：本篇所有代码都在片尾！！（醒目）

CMP

那么了解了这些，我们先列出一个list NAME 优势 劣势 splay LCT，序列之王 常数大，代码量稍大 RBT 自适应深度平衡树，速度在同类BST中遥遥领先 代码量大 SBT 代码简短，速度快，（退化版很好写） 功能平平，（退化版会被人字梯数据卡掉）

大体上来说，treap的敌人多为这三类。我们逆着证明treap是最强的。

TREAP VS SBT

就以常数来说，sbt与treap的常数皆为12左右，当然以数学证明\(log_n\) sbt的常数肯定要比用期望\(log_n\)的treap要稳很多，但是就我们平时直观所感觉的速度差，大多是因为**rand()**调用太耗时，所以解决此问题可以这样

1
2
3
4
inline int random(){
    static int seed=703; //seed可以随便取
    return seed=int(seed*48271LL%2147483647);
}

以数学的方法快速取得rand值 相关链接

这样一来比较不加读优，sbt为260ms+，treap为360ms+，速度已经很相近了。。。并且由于treap比sbt多一个rd数组存rand值，能有70%左右的速度已经非常可观了，但这不是重点。

Treap真正能够超越sbt的在于可以快速分裂与合并，这是sbt很难做到的，而且一旦去做，就必定会加入Father指针，这样会拖慢sbt旋转的速度。 详见代码 HERE

TREAP VS RBT

这可能是treap最大的敌人，速度足够碾压刚刚还得瑟的SBT（cqf的论文中虽然号称比AVL快[实际情况我还没有试过]，但是不敢说比RBT快），STL中set，map这些常用类型的底层实现方式。 这就是让人**恐惧并无法自拔（？）**的RBT（红黑树）！！ 那么这么强大的平衡树，为什么区区一介treap敢于挑战？ 在与。。。还记得我对RBT的描述吗？深度平衡树 那么就用你的优势成为你失败的伏笔！！！ 引出重量级 ##重量平衡树与后缀平衡树 丽洁姐的论文 可以发现能够支撑起平衡树向字符串领域进军的，就是treap！！ 复杂度在加入了一个类似于线段树的结构后并没有改变 \(log_n\)呢！暂且不论跳表的普及型以及删除时的恶心程度，一般非确定型跳表的空间复杂的是高于树形结构的BST的，其次跳表根本不是主流吧！！然后替罪羊树比起treap来说要难写一点（毕竟要重建笛卡尔树。。） 综上，treap可以完成许多深度平衡树（AVL、RBT）（SBT算什么？）无法做到的效果。

TREAP VS SPLAY

首先分裂与合并已经在讨论sbt时解决了，再者splay的常数又是在平衡数中排得上名号的（大根堆），单旋spaly直接被链式数据卡死，所以splay只有在序列与LCT上称王称霸。LCT有关 但真的是这样吗? 谈谈Treap与LCT，既然都能不旋转来分裂合并了，那么LCT自然是手到擒来。LCT例子 CDQZ本部的几个大神就是LCT只打treap。 所以splay能得瑟的就是序列之王这个名号了！ 光速打脸 NOI2005 维护数列 呵呵，虽然分裂合并式的Treap，速度慢，但是代码很好写，毕竟靠随机值无脑合并分裂啊。

结论（彩蛋？）

的确，treap在速度上输给了sbt、rbt（远远地），代码量上也仅仅与sbt持平（基础部分不到40行），分裂合并的常数值也比splay大。。 （观众：好像一无是处耶？） 但是treap反向证明了它自己可以做到那么多不同平衡树自己独具特点的功能，就好比金庸集各家之大成，虽未超越，但单单地将其聚合起来也足以称王了。 从重量平衡引申出的后缀平衡树，非旋转式引出分裂与合并，treap很弱，因为它不完整（从定义上就不完整），但也正是如此他对于OIer来说不是如RBT般的神，splay般的功能强大，sbt般的简洁飞速，所以它需要成长，对于没一点常数的争取，对于自身结构的改变，以及。。。。。本文最后的彩蛋！！

可持久化平衡树

这是多少OIer在可持久化treap发明前学平衡树的心结，那么强大的平衡树为什么没有能简单可持久化的方式呢？直到可持久化treap横空出世，震惊全球（夸张。），多少代OIer的愿望通过treap残缺的美在此得以实现。

code

普普通通的treap——rand()优化后

bzoj3224 普通平衡树 

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct data{
    int l,r,v,size,rnd,w;
}tr[100005];
int n,size,root,ans;
inline int randad(){
    static int seed=703; //seed可以随便取
    return seed=int(seed*48271LL%2147483647);
}
void update(int k)//更新结点信息
{
    tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w;
}
void rturn(int &k)
{
    int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;
    tr[t].size=tr[k].size;update(k);k=t;
}
void lturn(int &k)
{
    int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;
    tr[t].size=tr[k].size;update(k);k=t;
}
void insert(int &k,int x)
{
    if(k==0)
    {
        size++;k=size;
        tr[k].size=tr[k].w=1;tr[k].v=x;tr[k].rnd=randad();
        return;
    }
    tr[k].size++;
    if(tr[k].v==x)tr[k].w++;
    else if(x>tr[k].v)
    {
        insert(tr[k].r,x);
        if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k);
    }
    else
    {
        insert(tr[k].l,x);
        if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k);
    } 
}
void del(int &k,int x)
{
    if(k==0)return; 
    if(tr[k].v==x)
    {
        if(tr[k].w>1)
        {
            tr[k].w--;tr[k].size--;return;
        }
        if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r;
        else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd)
            rturn(k),del(k,x);
        else lturn(k),del(k,x);
    }
    else if(x>tr[k].v)
        tr[k].size--,del(tr[k].r,x);
    else tr[k].size--,del(tr[k].l,x);
}
int query_rank(int k,int x)
{
    if(k==0)return 0;
    if(tr[k].v==x)return tr[tr[k].l].size+1;
    else if(x>tr[k].v)
        return tr[tr[k].l].size+tr[k].w+query_rank(tr[k].r,x);
    else return query_rank(tr[k].l,x);
}
int query_num(int k,int x)
{
    if(k==0)return 0;
    if(x<=tr[tr[k].l].size)
        return query_num(tr[k].l,x);
    else if(x>tr[tr[k].l].size+tr[k].w)
        return query_num(tr[k].r,x-tr[tr[k].l].size-tr[k].w);
    else return tr[k].v;
}
void query_pro(int k,int x)
{
    if(k==0)return;
    if(tr[k].v<x)
    {
        ans=k;query_pro(tr[k].r,x);
    }
    else query_pro(tr[k].l,x);
}
void query_sub(int k,int x)
{
    if(k==0)return;
    if(tr[k].v>x)
    {
        ans=k;query_sub(tr[k].l,x);
    }
    else query_sub(tr[k].r,x);
}
int main()
{
    scanf("%d",&n);
    int opt,x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&opt,&x);
        switch(opt)
        {
        case 1:insert(root,x);break;
        case 2:del(root,x);break;
        case 3:printf("%d\n",query_rank(root,x));break;
        case 4:printf("%d\n",query_num(root,x));break;
        case 5:ans=0;query_pro(root,x);printf("%d\n",tr[ans].v);break;
        case 6:ans=0;query_sub(root,x);printf("%d\n",tr[ans].v);break;
        }
    }
    return 0;
}

序列treap

BZOJ1500 维护数列 

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
#define INF 2000000000  
#define N 500010  
struct Node;  
Node *null,*root;  
struct Node  
{  
    int w,sz,val,sum,ls,rs,ss,lzy1,lzy2;  
    Node *lft,*rht;  
    void split(int,Node*&,Node*&);  
    void same(int v)  
    {  
        if(this==null) return;  
        lzy2=val=v;  
        sum=v*sz;  
        ls=rs=ss=max(sum,v);  
    }  
    void rev()  
    {  
        if(this==null) return;  
        lzy1^=1;  
        swap(lft,rht);  
        swap(ls,rs);  
    }  
    Node *pushup()  
    {  
        sz=lft->sz+1+rht->sz;  
        sum=lft->sum+val+rht->sum;  
     
        ls=max(lft->ls,lft->sum+val+max(0,rht->ls));  
        rs=max(rht->rs,rht->sum+val+max(0,lft->rs));  
     
        ss=max(0,lft->rs)+val+max(0,rht->ls);  
        ss=max(ss,max(lft->ss,rht->ss));  
     
        return this;  
    }  
    Node *pushdown()  
    {  
        if(lzy1)  
        {  
            lft->rev();  
            rht->rev();  
            lzy1=0;  
        }  
        if(lzy2!=-INF)  
        {  
            lft->same(lzy2);  
            rht->same(lzy2);  
            lzy2=-INF;  
        }  
        return this;  
    }  
};  
Node *merge(Node *p,Node *q)  
{  
    if(p==null) return q;  
    if(q==null) return p;  
    if(p->w<q->w)  
    {  
        p->pushdown();  
        p->rht=merge(p->rht,q);  
        return p->pushup();  
    }  
    q->pushdown();  
    q->lft=merge(p,q->lft);  
    return q->pushup();  
}  
void Node::split(int need,Node *&p,Node *&q)  
{  
    if(this==null)  
    {  
        p=q=null;  
        return;  
    }  
    pushdown();  
    if(lft->sz>=need)  
    {  
        lft->split(need,p,q);  
        lft=null;  
        pushup();  
        q=merge(q,this);  
        return;  
    }  
    rht->split(need-(lft->sz+1),p,q);  
    rht=null;  
    pushup();  
    p=merge(this,p);  
    return;  
}  
Node data[N],*pool[N];  
int top,cnt;  
Node* newnode(int c)  
{  
    Node *x;  
    if(top) x=pool[top--];  
    else x=&data[cnt++];  
    x->lft=x->rht=null;  
    x->sz=1; x->lzy1=0; x->lzy2=-INF;  
    x->val=x->sum=x->ls=x->rs=x->ss=c;  
    x->w=rands();  
    return x;  
}  
void init()  
{  
    cnt=1; top=0;  
    null=&data[0];  
    null->sz=null->sum=0;  
    null->val=null->ls=null->rs=null->ss=-INF;  
    null->lzy1=0;  
    null->lzy2=-INF;  
    null->lft=null->rht=null;  
}  
//---------------------------------------------------------  
void erase(Node *rt)  
{  
    if(rt==null) return;  
    erase(rt->lft);  
    erase(rt->rht);  
    pool[++top]=rt;  
}  
int n,m;  
char ord[20];  
int a,b,c;  
int main ()  
{  
init();  
        root=null;  
        n=fastget();  
        m=fastget();  
        for(int i=0;i<n;i++)  
        {  
            a=fastget();  
            root=merge(root,newnode(a));  
        }  
        while (m--)  
        {  
            scanf("%s",ord);  
            Node *p,*q,*r,*s;  
            if(ord[0]=='I')  
            {  
                a=fastget();  
                n=fastget();  
                root->split(a,p,q);  
                for(int i=0;i<n;i++)  
                {  
                    b=fastget();  
                    p=merge(p,newnode(b));  
                }  
                root=merge(p,q);  
            }else if(ord[0]=='D')  
            {  
                a=fastget();  
                b=fastget();  
                b=a+b-1;  
                root->split(a-1,p,q);  
                q->split(b-a+1,r,s);  
                erase(r);  
                root=merge(p,s);  
            }else if(ord[0]=='M' && ord[2]=='K')  
            {  
                a=fastget();  
                b=fastget();  
                c=fastget();  
                b=b+a-1;  
                root->split(a-1,p,q);  
                q->split(b-a+1,r,s);  
                r->same(c);  
                root=merge(p,merge(r,s));  
            }else if(ord[0]=='R')  
            {  
                a=fastget();  
                b=fastget();  
                b=b+a-1;  
                root->split(a-1,p,q);  
                q->split(b-a+1,r,s);  
                r->rev();  
                root=merge(p,merge(r,s));  
            }else if(ord[0]=='G')  
            {  
                a=fastget();  
                b=fastget();  
                b=a+b-1;  
                root->split(a-1,p,q);  
                q->split(b-a+1,r,s);  
                fastput(r->sum);  
                root=merge(p,merge(r,s));  
            }  
            else if(ord[0]=='M') fastput(root->ss);  
        }  
        
    return 0;  
}

重量平衡树&后缀平衡树

BZOJ 3682: Phorni 

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &res){
	static char ch;T flag=1;
	while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
	while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag;
}
#define N 500010
#define LL long long
int n,m,len,type,lastans,x,y;
int ch[N][2],rd[N],cl[N],cnt,root;
LL rk[N];
inline int randlmy(){
	static int seed=173;
    return seed=int(seed*48271LL%2147483647);
}
int cmp(int x,int y){
	return cl[x]<cl[y]||(cl[x]==cl[y]&&rk[x-1]<rk[y-1]);
}
void rebuild(int &rt,LL l,LL r){
	if(!rt)return;
	rk[rt]=l+r;
	LL mid=(l+r)>>1;
	rebuild(ch[rt][0],l,mid);
	rebuild(ch[rt][1],mid,r);
	
}
void rotate(int &p,int d,LL l,LL r){
	int q=ch[p][d^1];
	ch[p][d^1]=ch[q][d];
	ch[q][d]=p;
	p=q;
	rebuild(p,l,r);
}
void insert(int &rt,LL l,LL r){
	LL mid=(r+l)>>1;
	if(!rt){rt=cnt;rk[rt]=l+r;return;}
	if(cmp(cnt,rt)){insert(ch[rt][0],l,mid);if(rd[ch[rt][0]]>rd[rt])rotate(rt,1,l,r);}
    else{insert(ch[rt][1],mid,r);if(rd[ch[rt][1]]>rd[rt])rotate(rt,0,l,r);}
}
void insert(int v){
	cl[++cnt]=v;
	rd[cnt]=randlmy()*randlmy();
	insert(root,1,1LL<<61);
}
#define R(rt) rt<<1|1
#define L(rt) rt<<1
int minn[N<<2],p[N];
void build(int rt,int l,int r){
	if(l==r)read(p[l]),minn[rt]=l;
	else{
		int mid=(l+r)>>1,lc=L(rt),rc=R(rt);
		build(lc,l,mid);
		build(rc,mid+1,r);
		minn[rt]=rk[p[minn[lc]]]<=rk[p[minn[rc]]]?minn[lc]:minn[rc];
	}
}
void updata(int rt,int l,int r,int id){
	if(l==r)return;
	int mid=(l+r)>>1,lc=L(rt),rc=R(rt);
	if(id<=mid)updata(lc,l,mid,id);
	else updata(rc,mid+1,r,id);
	minn[rt]=rk[p[minn[lc]]]<=rk[p[minn[rc]]]?minn[lc]:minn[rc];
}
int query(int rt,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return minn[rt];
	int mid=(l+r)>>1,lc=L(rt),rc=R(rt);
	if(qr<=mid)return query(lc,l,mid,ql,qr);
	if(ql>mid)return query(rc,mid+1,r,ql,qr);
	int vl=query(lc,l,mid,ql,qr),vr=query(rc,mid+1,r,ql,qr);
	return rk[p[vl]]<=rk[p[vr]]?vl:vr;
}
char s[N],cmd[5];
int main(){
	read(n),read(m),read(len),read(type);
	scanf("%s",s);
	for(register int i=1;i<=len;i++)
		insert(s[len-i]-'a');
	build(1,1,n);
	while(m--){
		scanf("%s",cmd);
		if(!type)lastans=0;
		if(cmd[0]=='I')
			read(x),insert(x^lastans),++len;
		else if(cmd[0]=='C')
			read(x),read(p[x]),updata(1,1,n,x);
		else
			read(x),read(y),
			printf("%d\n",lastans=query(1,1,n,x,y));
	}
	return 0;
}

可持久化Treap

POJ 3580 SuperMemo 

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
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<ctime>  
#include<cstdlib>  
#include<algorithm>  
using namespace std;  
struct treap_node{  
    treap_node *left,*right;  
    int val,fix,size,wgt,minn,adel,rdel;  
    treap_node(int val): val(val) {left=right=NULL; fix=rand(); wgt=size=1; minn=val; rdel=adel=0; }  
    int lsize()  
      {  
        if (left)  
          return left->size;  
        else   
          return 0;  
      }  
    int rsize()  
      {  
        if (right)  
          return right->size;  
        else  
          return 0;  
      }  
    void updata()  
      {  
        minn=val;  
        if (left)  
          minn=min(minn,left->minn+left->adel);  
        if (right)  
          minn=min(minn,right->minn+right->adel);  
      }  
    void pushdown()  
      {  
        treap_node *temp;  
        if (adel)  
          {  
            minn+=adel;  
            val+=adel;  
            if (left)  
              left->adel+=adel;  
            if (right)  
              right->adel+=adel;  
            adel=0;  
          }  
        if (rdel%2)  
          {  
            if (left==NULL||right==NULL)  
              {  
                if (left==NULL)  
                  {  
                    left=right;  
                    right=NULL;  
                  }  
                else  
                  {  
                    right=left;  
                    left=NULL;  
                  }  
              }  
            else  
              {  
                temp=left;  
                left=right;  
                right=temp;  
              }  
            if (left)  
            left->rdel+=rdel;  
            if (right)  
            right->rdel+=rdel;  
            rdel=0;  
          }  
        updata();  
      }  
    void Maintain()  
      {  
        size=wgt;  
        size+=lsize()+rsize();  
      }  
};  
int n,m;  
treap_node *root;  
typedef pair<treap_node*,treap_node*> droot;  
treap_node *merge(treap_node *a,treap_node *b)  
{  
    if (!a) return b;  
    if (!b) return a;  
    a->pushdown(); b->pushdown();  
    a->updata(); b->updata();  
    if (a->fix<b->fix)  
      {  
        a->right=merge(a->right,b);  
        a->updata();  
        a->Maintain();  
        return a;  
      }  
    else  
      {  
        b->left=merge(a,b->left);  
        b->updata();  
        b->Maintain();  
        return b;  
      }   
}  
droot split(treap_node *a,int k)  
{   
    if (!a) return droot(NULL,NULL);  
    droot y;  
    a->pushdown();   a->updata();  
    if (a->lsize()>=k)  
      {  
        y=split(a->left,k);  
        a->left=y.second;  
        a->updata();  
        a->Maintain();  
        y.second=a;  
      }  
    else  
      {  
        y=split(a->right,k-a->lsize()-1);  
        a->right=y.first;  
        a->updata();  
        a->Maintain();  
        y.first=a;  
      }  
    return y;  
}  
void insert(int k,int value)  
{  
    treap_node *temp;  
    droot y=split(root,k);  
    temp=new treap_node(value);  
    root=merge(merge(y.first,temp),y.second);  
}  
void del(int k)  
{  
    droot x,y;  
    x=split(root,k-1);  
    y=split(x.second,1);  
    root=merge(x.first,y.second);  
}  
int main()  
{  
    char s[20];  
    droot ai,bi,ci;  
    treap_node *temp;  
    int i,x,y,a,L,t;  
    scanf("%d",&n);  
    for (i=1;i<=n;++i)  
      {  
        scanf("%d",&x);  
        insert(i,x);  
      }  
    scanf("%d",&m);  
    for (i=1;i<=m;++i)  
      {  
        scanf("%s",&s);  
        if (s[0]=='A')  
          {  
            scanf("%d%d%d",&x,&y,&a);  
            ai=split(root,x-1);  
            bi=split(ai.second,y-x+1);  
            bi.first->adel+=a;  
            ai.second=merge(bi.first,bi.second);  
            root=merge(ai.first,ai.second);  
          }  
        if (s[0]=='I')  
          {  
            scanf("%d%d",&x,&a);  
            insert(x,a);  
          }  
        if (s[0]=='D')  
          {  
            scanf("%d",&x);  
            del(x);  
          }  
        if (s[0]=='R')  
          {  
            if (s[3]=='E')  
              {  
                scanf("%d%d",&x,&y);  
                ai=split(root,x-1);  
                bi=split(ai.second,y-x+1);    
                bi.first->rdel++;  
                ai.second=merge(bi.first,bi.second);  
                root=merge(ai.first,ai.second);  
              }  
            if (s[3]=='O')  
              {  
                scanf("%d%d%d",&x,&y,&a);  
                L=y-x+1;  
                a=(a%L+L)%L;  
                ai=split(root,x-1);   
                bi=split(ai.second,L);  
                ci=split(bi.first,L-a);  
                bi.first=merge(ci.second,ci.first);  
                ai.second=merge(bi.first,bi.second);  
                root=merge(ai.first,ai.second);  
              }    
          }  
        if (s[0]=='M')  
          {  
            scanf("%d%d",&x,&y);  
            ai=split(root,x-1);  
            bi=split(ai.second,y-x+1);   
            t=bi.first->minn;  
            ai.second=merge(bi.first,bi.second);  
            root=merge(ai.first,ai.second);  
            printf("%d\n",t);    
          }  
      }  
}

补一句，多年的超文本编辑器问题也解决了。。。。 TREAP最强！！

click it and link me

Launch CodeCogs Equation Editor