「HNOI2017」单旋

发表于
https://loj.ac/problem/2018

题目链接

「HNOI2017」单旋

做法

对于 $ splay $ 操作，模拟发现整棵树的形态不变且深度加一（除了 $ splay $ 的节点的子树深度不变）， $ splay $ 的点深度变为 $ 1 $ 。
用线段树维护每个权值深度。
对于操作 $ 1 $ ，用 $ set $ 维护已经存在的节点，新插入的节点父亲一定为它前驱、后继中的一个。
对于操作 $ 2, 3, 4, 5 $ ，模拟 $ splay $ 第一次和最后一次旋转子树操作，用线段树维护深度即可。
时间复杂度 $ O(n \log n) $ 。 

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
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 100010;
int m, p[N], lp;
struct Q { int opt, x; }; Q q[N];
int tr[N * 4];
int rt, fa[N], ch[2][N];
set<int> s;

template<typename T> void gi(T &x) {
	x = 0; register char c = getchar(), pre = 0;
	for(; c < '0' || c > '9'; pre = c, c = getchar());
	for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10ll + (c ^ 48);
	if(pre == '-') x = -x;
}
void pushdown(int u) {
	if(tr[u]) tr[u * 2] += tr[u], tr[u * 2 + 1] += tr[u], tr[u] = 0;
}
void mdy(int u, int l, int r, int x, int w) {
	if(l >= r) { tr[u] = w; return ; }
	int mid = (l + r) >> 1; pushdown(u);
	x <= mid ? mdy(u * 2, l, mid, x, w) : mdy(u * 2 + 1, mid + 1, r, x, w);
}
void mdy(int u, int l, int r, int L, int R, int w) {
	if(L <= l && r <= R) { tr[u] += w; return ; }
	int mid = (l + r) >> 1; pushdown(u);
	if(L <= mid) mdy(u * 2, l, mid, L, R, w);
	if(R > mid) mdy(u * 2 + 1, mid + 1, r, L, R, w);
}
int qry(int u, int l, int r, int x) {
	if(l >= r) return tr[u];
	int mid = (l + r) >> 1; pushdown(u);
	return x <= mid ? qry(u * 2, l, mid, x) : qry(u * 2 + 1, mid + 1, r, x);
}
int insert(int x) {
	set<int>::iterator it = s.insert(x).fst;
	if(!rt) { rt = x, mdy(1, 1, lp, x, 1); return 1; }
	if(it != s.begin()) {
		--it; if(!ch[1][*it]) ch[1][*it] = x, fa[x] = *it; ++it;
	}
	if(!fa[x]) ++it, ch[0][*it] = x, fa[x] = *it;
	int dep = qry(1, 1, lp, fa[x]) + 1; mdy(1, 1, lp, x, dep); return dep;
}
int splaymin(int x) {
	int dep = qry(1, 1, lp, x); if(x == rt) return dep;
	if(x + 1 <= fa[x] - 1) mdy(1, 1, lp, x + 1, fa[x] - 1, -1);
	++tr[1], mdy(1, 1, lp, x, 1);
	ch[0][fa[x]] = ch[1][x], fa[ch[1][x]] = fa[x];
	fa[rt] = x, fa[x] = 0, ch[1][x] = rt, rt = x; return dep;
}
int splaymax(int x) {
	int dep = qry(1, 1, lp, x); if(x == rt) return dep;
	if(x - 1 >= fa[x] + 1) mdy(1, 1, lp, fa[x] + 1, x - 1, -1);
	++tr[1], mdy(1, 1, lp, x, 1);
	ch[1][fa[x]] = ch[0][x], fa[ch[0][x]] = fa[x];
	fa[rt] = x, fa[x] = 0, ch[0][x] = rt, rt = x; return dep;
}
int erasemin(int x) {
	int dep = splaymin(x); --tr[1];
	rt = ch[1][x], fa[rt] = 0, ch[1][x] = 0, s.erase(x); return dep;
}
int erasemax(int x) {
	int dep = splaymax(x); --tr[1];
	rt = ch[0][x], fa[rt] = 0, ch[0][x] = 0, s.erase(x); return dep;
}
int main() {
	gi(m);
	rep(i, 1, m) { gi(q[i].opt); if(q[i].opt == 1) gi(q[i].x), p[++lp] = q[i].x; }
	sort(p + 1, p + lp + 1), lp = unique(p + 1, p + lp + 1) - p - 1;
	rep(i, 1, m)
		if(q[i].opt == 1) q[i].x = lower_bound(p + 1, p + lp + 1, q[i].x) - p;
	rep(i, 1, m) {
		if(q[i].opt == 1) printf("%d\n", insert(q[i].x));
		if(q[i].opt == 2) printf("%d\n", splaymin(*s.begin()));
		if(q[i].opt == 3) printf("%d\n", splaymax(*(--s.end())));
		if(q[i].opt == 4) printf("%d\n", erasemin(*s.begin()));
		if(q[i].opt == 5) printf("%d\n", erasemax(*(--s.end())));
	}
	return 0;
}