GGAutomaton's Blog
0%

splay模板

发表于 分类于 ，

https://www.luogu.org/problemnew/show/P4146

3种操作：
1.将[L,R]这个区间内的所有数加上V。
2.将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。
3.求[L,R]这个区间中的最大值。

由于交换两个子树必定会改变BST的性质
所以不能用key值做find
只能用size表示数组元素下标
查询下标为k的元素用find_Kth

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> //for swap();
using namespace std;
int fa[50005],ch[50005][2],size[50005];
bool reversed[50005];
int tag[50005],mx[50005],val[50005];//特别注意0点初始化的值，而且所有操作不能修改它
int num,root;
int n,m;
inline void update(int x) {
	int lson=ch[x][0],rson=ch[x][1];
    size[x]=size[lson]+size[rson]+1;
    mx[x]=max(val[x],max(mx[lson],mx[rson]));
}
inline void pushdown(int x) {
	if (reversed[x]) {
		if (ch[x][0]) reversed[ch[x][0]]^=1;
		if (ch[x][1]) reversed[ch[x][1]]^=1;
		swap(ch[x][0],ch[x][1]);//#include<algorithm>
		reversed[x]=0;
	}
	if (tag[x]) {
		int lson=ch[x][0],rson=ch[x][1];
		if (lson) {
			tag[lson]+=tag[x];
			val[lson]+=tag[x];
			mx[lson]+=tag[x];
		}
		if (rson) {
			tag[rson]+=tag[x];
			val[rson]+=tag[x];
			mx[rson]+=tag[x];
		}
		tag[x]=0;
	}
}
inline void rotate(int x) {
	int fa1=fa[x],fa2=fa[fa1],side=(ch[fa[x]][1]==x);
	pushdown(fa1);pushdown(x);
	ch[fa1][side]=ch[x][side^1];fa[ch[fa1][side]]=fa1;
	fa[fa1]=x;ch[x][side^1]=fa1;
	fa[x]=fa2;
	if (fa2) ch[fa2][ch[fa2][1]==fa1]=x;
	update(fa1);update(x);
}
inline void splay(int x,int goal) {//由于Kth里面做了pushdown，这里可以不做
    while (fa[x]!=goal) {
        int fa1=fa[x],fa2=fa[fa1];
        if (fa2!=goal) {
			if ((ch[fa2][0]==fa1)^(ch[fa1][0]==x)) rotate(x);
			else rotate(fa1);
		}
        rotate(x);
    }
    if (goal==0) root=x;
}
inline int Kth(int k) {
    int p=root;
    while (666233) {
        pushdown(p);
        if (size[ch[p][0]]>=k) p=ch[p][0];
        else if (size[ch[p][0]]+1==k) return p;
        else k-=size[ch[p][0]]+1,p=ch[p][1];
    }
}
void build(int &p,int l,int r,int ff) {
	if (l>r) {p=0;return;}
	p=++num;
	fa[p]=ff;
	if (l==r) {
		size[p]=1;
		ch[p][0]=ch[p][1]=0;
		if (l==0 || l==n+1) mx[p]=val[p]=-1e9;
		return;
	}
	int mid=(l+r)>>1;
	if (mid==0 || mid==n+1) mx[p]=val[p]=-1e9;
	build(ch[p][0],l,mid-1,p);
	build(ch[p][1],mid+1,r,p);
	update(p);
}
int main() {
	cin >> n >> m;
	build(root,0,n+1,0);mx[0]=-1e9;
	for (int i=1;i<=m;i++) {
		int op,x,y,v=0;
		scanf("%d%d%d",&op,&x,&y);
		if (op==1) scanf("%d",&v);
		int la=Kth(x);splay(la,0);//x+1-1
		int ne=Kth(y+2);splay(ne,la);//y+1+1
		int p=ch[ne][0];
		if (op==1) tag[p]+=v,mx[p]+=v,val[p]+=v;
		else if (op==2) reversed[p]^=1;
		else printf("%d\n",mx[p]);
	}
	return 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
inline void ins(int c) {
    int p=root,ff=0;
    while (p && key[p]!=c) {
        ff=p;
        p=ch[p][c>key[p]];
    }
    if (p) cnt[p]++;
    else {
        p=++num;
        if (ff) ch[ff][c>key[ff]]=p;//如果父节点非0
	else root=p;
        ch[p][0]=ch[p][1]=0;
        fa[p]=ff;
        key[p]=c;
        cnt[p]=size[p]=1;
    }
    splay(p,0);
}

inline void find(int c) { //查找c的位置，并将其旋转到根节点
    int p=root;
    while (ch[p][c>key[p]] && c!=key[p]) p=ch[p][c>key[p]];
    splay(p,0);
}

inline int pre_nxt(int c,int op) { //查找c的前驱(0)或者后继(1)
    find(c);
    int p=root;
	if (key[p]!=c) { //c不存在需要特判
		if (key[p]>c && op) return p;
	    if (key[p]<c && !op) return p;
	}
    p=ch[p][op];
    while (ch[p][op^1]) p=ch[p][op^1];
    return p;
}

inline void del(int c) {
	find(c);
	if (key[root]!=c) return;
	if (cnt[root]>1) {cnt[root]--;size[root]--;return;}
	if (!ch[root][0] && !ch[root][1]) {root=0;return;}
	if (!ch[root][0]) {root=ch[root][1];fa[root]=0;return;}
	if (!ch[root][1]) {root=ch[root][0];fa[root]=0;return;}
	int p=pre_nxt(c,0),oldroot=root;
	splay(p,0);
	fa[ch[oldroot][1]]=root;
	ch[root][1]=ch[oldroot][1];
	update(root);
}

还有合并，拆分等操作未写出