splay模板

Posted on | In

基本平衡树操作

splay的旋转x，就是把它和fa[x]在不违反定义的情况下互换父子关系，左儿子变左父亲，例如。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+2;
int cnt[maxn],ch[maxn][2],fa[maxn],val[maxn],sz[maxn],rt,tot;

struct Splay{
    void clear(int x){
        ch[x][0]=ch[x][1]=fa[x]=sz[x]=cnt[x]=0;
    }
    void pushup(int x){
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
    }
    bool get(int x){
        return x==ch[fa[x]][1];
    }
    void rotate(int x){ //在不破坏二叉搜索性条件下改变x父子关系
        int y=fa[x],z=fa[y],chk=get(x);
        ch[y][chk]=ch[x][chk^1];
        fa[ch[x][chk^1]]=y;
        ch[x][chk^1]=y;
        fa[y]=x;
        if(z) ch[z][y==ch[z][1]]=x;
        fa[x]=z;
        pushup(y);
        pushup(x);
    }
    void splay(int x){
        for(int f=fa[x];f=fa[x],f;rotate(x)){
            if(fa[f])
                rotate(get(x)==get(f)?f:x);
        }
        rt=x;
    }
    void ins(int k){
        if(!rt){
            val[++tot]=k;
            cnt[tot]++;
            rt=tot;
            pushup(rt);
            return;
        }
        int cur=rt,f=0;
        while(1){
            if(val[cur]==k){
                cnt[cur]++;
                pushup(cur);
                pushup(f);
                splay(cur);
                break;
            }
            f=cur;
            cur=ch[cur][val[cur]<k];
            if(!cur){
                val[++tot]=k;
                cnt[tot]++;
                fa[tot]=f;
                ch[f][val[f]<k]=tot;
                pushup(tot);
                pushup(f);
                splay(tot);
                break;
            }
        }
    }
    //查x的排名
    int rk(int x){
        int res=0,cur=rt;
        while(1){
            if(x<val[cur]){
                cur=ch[cur][0];
            }else{
                res+=sz[ch[cur][0]];
                if(x==val[cur]){
                    splay(cur);
                    return res+1;
                }
                res+=cnt[cur];
                cur=ch[cur][1];
            }
        }
        return res;
    }
    //查排名k的数
    int kth(int k){
        int cur=rt;
        while(1){
            if(ch[cur][0]&&k<=sz[ch[cur][0]])
                cur=ch[cur][0];
            else{
                k-=cnt[cur]+sz[ch[cur][0]];
                if(k<=0){
                    splay(cur);
                    return val[cur];
                }
                cur=ch[cur][1];
            }
        }
    }
    //查x的前驱编号，先插入x，再pre()，再删除x
    int pre(){
        //找x左子树中最大节点
        int cur=ch[rt][0];
        while(ch[cur][1])
            cur=ch[cur][1];
        splay(cur);
        return cur;
    }
    int nxt(){
        int cur=ch[rt][1];
        while(ch[cur][0])
            cur=ch[cur][0];
        splay(cur);
        return cur;
    }

    void del(int k){
        rk(k);
        if(cnt[rt]>1){
            cnt[rt]--;
            pushup(rt);
            return;
        }
        if(!ch[rt][0]&&!ch[rt][1]){
            clear(rt);
            rt=0;
            return;
        }
        if(!ch[rt][0]){
            int cur=rt;
            rt=ch[cur][1];
            fa[rt]=0;
            clear(cur);
            return;
        }
        if(!ch[rt][1]){
            int cur=rt;
            rt=ch[cur][0];
            fa[rt]=0;
            clear(cur);
            return;
        }
        int cur=rt,x=pre();
        splay(x);
        fa[ch[cur][1]]=x;
        ch[x][1]=ch[cur][1];
        clear(cur);
        pushup(rt);
    }
}tree;


int main(){
    int n;
    cin>>n;
    for(int i=1,opt,x;i<=n;i++){
        cin>>opt>>x;
        switch(opt){
        case 1:
            tree.ins(x);
            break;
        case 2:
            tree.del(x);
            break;
        case 3:
            cout<<tree.rk(x)<<endl;
            break;
        case 4:
            cout<<tree.kth(x)<<endl;
            break;
        case 5:
            tree.ins(x);
            cout<<val[tree.pre()]<<endl;
            tree.del(x);
            break;
        case 6:
            tree.ins(x);
            cout<<val[tree.nxt()]<<endl;
            tree.del(x);
            break;
        default:
            ;
        }
    }
}

做区间翻转

由于splay操作可以将任一节点在不违反定义的情形下移动到根，splay树由此多了一些用途，例如维护区间翻转。

https://www.luogu.com.cn/problem/P3391

对于splay操作稍作修改，可以使得某节点上升至任一位置。

然后我们用原序列的下标建树。需要翻转某个区间时，先将l-1splay到根的位置，再将r+1splay到根的右儿子上，现在r+1的左儿子就是要翻转的区间。

对于一棵树，翻转区间就是从上而下交换每个节点的左右儿子，可以打lazy标记，实现log复杂度。

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
#include<bits/stdc++.h>
using namespace std;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^48); ch=getchar();}
    return x*f;
}

const int maxn=1e5+2;
#define lson (ch[o][0])
#define rson (ch[o][1])
int ch[maxn][2],rev[maxn],size[maxn],fa[maxn],val[maxn],rt,n,m;

void pushup(int o){
    size[o]=size[lson]+size[rson]+1;
}
void pushdown(int o){
    if(rev[o]){
        swap(lson,rson);
        rev[lson]^=1;rev[rson]^=1;rev[o]=0;
    }
}

void build(int l,int r,int o){
    if(l>r)
        return;
    int mid=(l+r)>>1;
    if(mid<o){
        lson=mid;
    }else{
        rson=mid;
    }
    fa[mid]=o;size[mid]=1;
    if(l==r)
        return;
    build(l,mid-1,mid);
    build(mid+1,r,mid);
    pushup(mid);
}

bool get(int x){
    return x==ch[fa[x]][1];
}
void rotate(int x){ //在不破坏二叉搜索性条件下改变x父子关系
    int y=fa[x],z=fa[y],chk=get(x);
    pushdown(y);
    pushdown(x);
    ch[y][chk]=ch[x][chk^1];
    fa[ch[x][chk^1]]=y;
    ch[x][chk^1]=y;
    fa[y]=x;
    if(z) ch[z][y==ch[z][1]]=x;
    fa[x]=z;
    pushup(y);
    pushup(x);
}
void splay(int x,int goal){	//goal是目标位置的父亲
    for(int f;f=fa[x],f!=goal;rotate(x)){
        if(fa[f]!=goal)
            rotate(get(x)==get(f)?f:x);
    }
    if(goal==0)
        rt=x;
}

int find(int k,int o){
    pushdown(o);
    if(k==size[lson]+1){
        return o;
    }else if(k<=size[lson]){
        return find(k,lson);
    }else{
        return find(k-(size[lson]+1),rson);
    }
}

void reverse(int L,int R){
    splay(L,0);
    splay(R,rt);
    rev[ch[R][0]]^=1;
}

void print(int o){
    pushdown(o);
    if(lson)
        print(lson);
    if(val[o]&&val[o]<=n)
        printf("%d ",val[o]);
    if(rson)
        print(rson);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n+2;i++)
        val[i]=i-1;
    rt=(n+3)>>1;
    build(1,n+2,rt);
    fa[rt]=0;	//build在根的处理上重复了一次，要重新把根的父节点设为0，要不splay会无法停止
    for(int i=1,l,r;i<=m;i++){
        cin>>l>>r;
        int L=find(l,rt);
        int R=find(r+2,rt);
        reverse(L,R);
    }
    print(rt);
}