Splay学习笔记

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141186465

Splay的两个关键函数，rotate和splay

rotate就是正常的旋转。

splay(x,target)表示把x旋转为target的子节点

这里需要分讨，对于x的父亲y和祖父z

  • 若 z = target， 则直接转x

  • 若 x 与 y 方向相同，先转y，后转x

  • 若 x 与 y 方向不同，转2次x

对于每一个操作，只要访问一个点，都要splay一次。而且要更新访问的最下面的点。

同时对结构改变时要考虑会不会搞到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
struct Splay {
	int son[N][2], fa[N], cnt[N], w[N], a[N], root, tot; 
	int ls(int x) { return son[x][0]; }
	int rs(int x) { return son[x][1]; }
	int zh(int x) { return rs(fa[x]) == x; }
	void push_up(int x) { if(x) w[x] = cnt[x] + w[ls(x)] + w[rs(x)]; }
	void print(int x) {
		if(!x) return ; 
		printf("%d [%d] -> [%d %d]\n", a[x], w[x], a[ls(x)], a[rs(x)]); 
		print(ls(x)); print(rs(x)); 
		if(x == root) printf("----------------\n"); 
	}
	void rotate(int x) {
		int y = fa[x], z = fa[y]; 
		int k = zh(x), w = son[x][k ^ 1]; 
		if(z) son[z][zh(y)] = x, fa[x] = z; else fa[x] = 0; 
		if(w) son[y][k] = w, fa[w] = y; else son[y][k] = 0; 
		son[x][k ^ 1] = y; fa[y] = x; 
		push_up(y); push_up(x); 
	}
	void splay(int x, int target = 0) {
		while(fa[x] != target) {
			int y = fa[x], z = fa[y]; 
			if(z != target) {
				if(zh(x) == zh(y)) rotate(y); 
				else rotate(x); 
			}
			rotate(x); 
		}
		if(!target) root = x; 
	}
	void insert(int x) {
		int now = root, las = 0; 
		while(now && a[now] != x) 
			las = now, now = son[now][x > a[now]]; 
		if(!now) {
			now = ++tot; 
			if(las) son[las][x > a[las]] = now; 
			fa[now] = las; a[now] = x; 
		}
		++cnt[now]; ++w[now]; 
		splay(now); 
	}
	int find_last(int x) {
		int now = root, ans = 0, las = 0; 
		while(now) {
			las = now; 
			if(a[now] >= x) now = ls(now); 
			else ans = now, now = rs(now); 
		}
		splay(las); 
		return ans; 
	}
	int find_next(int x) {
		int now = root, ans = 0, las = 0; 
		while(now) {
			las = now; 
			if(a[now] <= x) now = rs(now); 
			else ans = now, now = ls(now); 
		}
		splay(las); 
		return ans; 
	}
	int cha_x_rank(int x) {
		int u = find_last(x + 1); splay(u);
		int ans = w[u] - w[rs(u)]; 	 
		if(a[u] == x) ans -= cnt[u]; 
		return ans + 1; 
	}
	int cha_rank(int now) {
		int x = root, las = 0; 
		while(x) {
			if(w[ls(x)] >= now) x = ls(x); 
			else if(w[ls(x)] + cnt[x] >= now) return splay(x), x; 
			else now -= (w[ls(x)] + cnt[x]), x = rs(x); 
		}
		assert(x); return 0; 
	}
	void join(int x, int y) {
		fa[x] = fa[y] = 0; 
		while(rs(x)) x = rs(x); 
		if(x) splay(x), son[x][1] = y, fa[y] = x;
		else root = y; 
		push_up(x); 
	}
	void del(int x) {
		int u = find_last(x + 1); splay(u); 
		if(cnt[u] > 1) return --cnt[u], --w[u], void(); 
		join(ls(u), rs(u)); 
	}
}T;

例1 文艺平衡树

涉及到打tag操作

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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)

#else
 #define debug(...) void(0)

#endif
//#define int long long
inline 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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)

#define pb push_back

#define fi first

#define se second

//#define M
//#define mo
#define N 100010

int n, m, i, j, k;

struct Splay {
	int a[N], son[N][2], fa[N], w[N], root, tot; 
	int tag[N]; 
	int ls(int x) { return son[x][0]; }
	int rs(int x) { return son[x][1]; }
	int zh(int x) { return son[fa[x]][1] == x; }
	void push_down(int x) {
		if(!tag[x]) return ; 
		int &u = son[x][0], &v = son[x][1]; 
		if(u) tag[u] ^= 1; 
		if(v) tag[v] ^= 1; 
		swap(u, v); 
		tag[x] = 0; 
	}
	void print(int x) {
		if(!x) return ; 
		push_down(x); 
		print(son[x][0]); 
		if(a[x] != 0 && a[x] != n + 1) 
			printf("%d ", a[x]); 
		print(son[x][1]); 
	}
	void print1(int x) {
		if(!x) return ; 
		push_down(x); 
		printf("%d[%d] -> [%d %d]\n", a[x], w[x], a[son[x][0]], a[son[x][1]]); 
		print1(son[x][0]); 
		print1(son[x][1]); 
		if(x == root) printf("-------------\n"); 
	}
	void push_up(int x) {
//		if(x > 0) return ; 
		w[x] = 1 + w[son[x][0]] + w[son[x][1]]; 
	}
	void rotate(int x) {
		int y = fa[x], z = fa[y]; 
		int k = zh(x), w = son[x][k ^ 1]; 
		push_down(z); push_down(y); push_down(x); 
		if(z) son[z][zh(y)] = x, fa[x] = z; else fa[x] = 0; 
		if(w) son[y][k] = w, fa[w] = y; else son[y][k] = 0; 
		son[x][k ^ 1] = y; fa[y] = x; 
		push_up(y); push_up(x); 
	}
	void splay(int x, int target = 0) {
		while(fa[x] != target) {
			int y = fa[x], z = fa[y]; 
//			debug("%d %d %d\n", x, y, z); 
			push_down(z); push_down(y); push_down(x); 
			if(z != target) {
				if(zh(x) == zh(y)) rotate(y); 
				else rotate(x); 
			}
			rotate(x); 
		}
		if(!target) root = x; 
	}
	void insert(int x) {
		int now = root, las = 0; 
		while(now) las = now, now = son[now][x > a[now]]; 
		now = ++tot; 
		if(las) son[las][x > a[las]] = now; 
		fa[now] = las; son[now][0] = son[now][1] = 0; w[now] = 1; a[now] = x; 
		if(!root) root = now; 
		splay(now); 
//		debug(">> %d[%d]\n", root, a[root]); 
	}
	int find(int x, int y) {
		push_down(x); 
//		debug("%d %d\n", x, y); 
		if(w[son[x][0]] >= y) return find(son[x][0], y); 
		if(w[son[x][0]] + 1 == y) return x; 
		return find(son[x][1], y - w[son[x][0]] - 1); 
	}
	void reverse(int l, int r) {
		++l; ++r; 
		int u = find(root, l - 1);
		splay(u); 
//		print1(root); 

		int v = find(root, r + 1); 
//		debug(">>>> %d [%d]\n", v, r + 1); 
		splay(v, u); 
//		print1(root); 
		tag[son[v][0]] = 1; 
	}
}T;

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); m = read(); 
	for(i = 0; i <= n + 1; ++i) T.insert(i); 
//	T.print1(T.root); 
	for(i = 1; i <= m; ++i) { 
		int l = read(), r = read(); 
		T.reverse(l, r); 
//		T.print1(T.root); 
//		T.print(T.root); printf("----\n"); 
	}
//	printf("\n"); 
	T.print(T.root); 
	return 0;
}



例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
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)

#else
 #define debug(...) void(0)

#endif
#define int long long

inline 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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)

#define pb push_back

#define fi first

#define se second

//#define M
//#define mo
#define N 500010

int n, m, i, j, k, T, x;
int ans, a[N]; 

struct Splay {
	int a[N], son[N][2], fa[N], root, tot, cnt[N]; 
	int ls(int x) { return son[x][0]; }
	int rs(int x) { return son[x][1]; }
//	int (int x) { return fa[x]; }
	int zh(int x) { return rs(fa[x]) == x; }
	void print(int x) {
		if(!x) return ; 
		printf("%lld(%lld) : [%lld %lld]\n", x, a[x], a[son[x][0]], a[son[x][1]]); 
		print(son[x][0]);
		print(son[x][1]);
		if(x == root) printf("---------------\n"); 
	}
	void rotate(int x) {
		int y = fa[x], z = fa[y]; 
		int k = zh(x), w = son[x][k ^ 1]; 
		if(z) son[z][zh(y)] = x, fa[x] = z; else fa[x] = 0; 
		son[x][k ^ 1] = y; fa[y] = x; 
		if(w) son[y][k] = w, fa[w] = y; else son[y][k] = 0; 
	}
	void splay(int x, int target = 0) {
		while(fa[x] != target) {
			int y = fa[x], z = fa[y]; 
			if(z != target) {
//				printf("eeeeeeeee"); 
//`				debug("[%lld %lld]\n", zh(x), zh(y)); 
				if(zh(x) == zh(y)) rotate(y); 
				else rotate(x); 
//				if(x == 4) print(root); 
			}
			rotate(x); 
//			if(x == 4) print(root); 
		}
		if(!target) root = x; 
	}
	void insert(int x) {
		int nw = root, las = 0; 
		while(nw && a[nw] != x) 
			las = nw, nw = son[nw][x > a[nw]]; 
		if(!nw) {
//			if(i == 2) printf("%lld %lld\n", las, nw); 
			nw = ++tot; 
			if(las) son[las][x > a[las]] = nw; 
			son[nw][0] = son[nw][1] = 0; a[nw] = x; fa[nw] = las; 
			if(!root) root = nw; 
		}
		++cnt[nw]; 
//		if(x == 37) print(root); 
		splay(nw); 
	}
	int qry(int x) {
		if(cnt[root] > 1) return 0; 
		int ans = 1e18, u = root; 
		u = son[u][0]; 
		while(u) {
			ans = min(ans, abs(x - a[u]));  
			u = son[u][1]; 
		}
		u = root; u = son[u][1]; 
		while(u) {
			ans = min(ans, abs(x - a[u]));  
			u = son[u][0]; 
		}
//		if(ans == 1e18) printf("%lld %lld[%lld %lld] %lld %lld\n", i, x, son[u][0], son[u][1], tot, root); 
//		assert(ans != 1e18); 
		debug("(%lld)[%lld] %lld %lld\n", u, x, a[son[u][0]], a[son[u][1]]); 
		return ans; 
	}
}splay;

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); 
//	n = 2; a[1] = 76633; a[2] = 76523; 
	for(i = 1; i <= n; ++i) {
		a[i] = read(); 
		splay.insert(a[i]); 
		if(i == 1) ans += a[i]; 
		else ans += splay.qry(a[i]); 
//		splay.print(splay.root); 
	}
	printf("%lld", ans); 
	return 0;
}



例3 维护集合

在这里插入图片描述

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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)

#else
 #define debug(...) void(0)

#endif
#define int long long

inline 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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)

#define pb push_back

#define fi first

#define se second

//#define M
//#define mo
#define N 100010

int n, m, i, j, k;
int ans, bas, Miv; 
char op[2]; 

struct Splay {
	int a[N], son[N][2], fa[N], root, cnt[N], w[N], tot; 
	int ls(int x) { return son[x][0]; }
	int rs(int x) { return son[x][1]; }
	int zh(int x) { return son[fa[x]][1] == x; }
	void push_up(int x) {
		w[x] = cnt[x] + w[son[x][0]] + w[son[x][1]]; 
	}
	void print(int x) {
		if(!x) return ; 
		printf("%d[%d] -> [%d %d]\n", a[x] + bas, w[x], a[son[x][0]] + bas, a[son[x][1]] + bas); 
		print(son[x][0]); print(son[x][1]); 
		if(x == root) printf("---------------------\n"); 
	}
	void rotate(int x) {
		int y = fa[x], z = fa[y]; 
		int k = zh(x), w = son[x][k ^ 1]; 
		if(z) son[z][zh(y)] = x, fa[x] = z; else fa[x] = 0; 
		if(w) son[y][k] = w, fa[w] = y; else son[y][k] = 0; 
		son[x][k ^ 1] = y; fa[y] = x; 
		push_up(y); push_up(x); 
	}
	void splay(int x, int target = 0) {
		while(fa[x] != target) {
			int y = fa[x], z = fa[y]; 
			if(z != target) {
				if(zh(x) == zh(y)) rotate(y); 
				else rotate(x); 
			}
			rotate(x); 
		}
		if(!target) root = x; 
	}
	void insert(int x) {
		int now = root, las = 0; 
		while(now && a[now] != x) 
			las = now, now = son[now][x > a[now]];
//		debug("aaaaaaaaaaaaa\n"); 
		if(!now) {
			now = ++tot; 
			if(las) son[las][x > a[las]] = now; 
			fa[now] = las; son[now][0] = son[now][1] = 0; a[now] = x; 
		}
		if(x != 1e12) ++cnt[now]; 
		if(!root) root = now; 
		splay(now); 
	}
	int find1(int x, int k) {
		int las = 0; 
		while(x) {
			if(w[son[x][0]] + cnt[x] >= k && k > w[son[x][0]]) return x; 
			las = x; 
			if(w[son[x][0]] >= k) x = son[x][0]; 
			else k -= (w[son[x][0]] + cnt[x]), x = son[x][1]; 
		}
		return las; 
	}
//	 int find1(int x, int k) {
//        if (w[son[x][0]] >= k)
//            return find1(son[x][0], k);
//        if (w[son[x][0]] + cnt[x] == k)
//            return x;
//        return find1(son[x][1], k - (w[son[x][0]] + cnt[x]));
//    }
	int qry(int k) {
		if(k > w[root]) return -1 - bas; 
		k = w[root] - k + 1; 
		int u = find1(root, k); splay(u); 
		return a[u]; 
	}
	int find2(int x, int k) {
		int las = 0, ans = 0; 
		while(x) {
			if(a[x] == k) return x; 
			if(a[x] >= k) ans = x; 
			las = x; 
			if(a[x] < k) x = son[x][1]; 
			else if(a[x] > k) x = son[x][0]; 
		}
		return ans; 
	}
//	int find2(int x, int k) {
//        if (a[x] == k)
//            return x;
//        if (a[x] < k)
//            return son[x][1] ? find2(son[x][1], k) : x;
//        if (a[x] > k) {
//            int y = (son[x][0] ? find2(son[x][0], k) : x);
//            return a[y] >= k ? y : x;
//        }
//    }
	int check(int miv) {
		int u = find2(root, miv); splay(u); 
		int d = w[son[u][0]]; son[u][0] = 0; push_up(u); 
		return d; 
	}
}T;

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); Miv = read(); T.insert(1e12); //T.print(T.root); 
	for(i = 1; i <= n; ++i) {
		scanf("%s", op); k = read(); 
//		debug("%c %d\n", op[0], k); 
		if(op[0] == 'I') {
			k -= bas; if(k < Miv) continue; 
			T.insert(k); 
		}
//		T.print(T.root); 
		if(op[0] == 'A') bas += k, Miv -= k; 
		if(op[0] == 'S') bas -= k, Miv += k, ans += T.check(Miv); 
		if(op[0] == 'F') printf("%lld\n", T.qry(k) + bas); 
	}
	printf("%lld\n", ans); 
	return 0;
}