【线段树】洛谷 P3369 【模板】普通平衡树
2021-04-11 18:42:00 # ACM

本题使用动态开点权值线段树…

数据范围是 $[-1e7,1e7]$ ，所以将其 $+(1e7+1)$ 让范围映射到 $[1,2e7+1]$ ,这样就在 $[1,2e7+1]$ 构建权值线段树，记 $2e7+1$ 为 $MAXN$；

先考虑前面 $4$ 种操作

插入和删除操作就是在线段树的叶子节点（递归的最底层）的位置 $+-1$，表示该点的个数，向上 $push_up$ 维护区间 $[L,R]$ 拥有的数字个数

根据所给数字，这里记作$tar$，求排名：就是求区间 $[1,tar-1]$ 有多少个数字，求出来要记得 $+1$，因为是 $tar$ 的排名

根据排名求数字，可以通过二分数字，对于每一个数字求排名，这样就可以用到步骤三写的函数

找前驱后继，这里记 $tar$ 为所要找的数字：

除了以上维护的区间数字个数 $cnt$，再维护两个信息区间最大值 $maxn$ 和区间最小值 $minn$

找前驱就是 $[1,tar-1]$ 找一个最大值，找后继就是 $[tar+1,MAXN]$ 找一个最小值

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
#include <bits/stdc++.h>
using namespace std;
#define MS 100009
#define ls rt<<1
#define rs rt<<1|1
#define LL long long 
#define MAXN 20000009

int n,m;
int tot;
int root;
struct node{
	int l,r;
	int cnt;
	int maxn,minn;
}p[MS*20];

void push_up(int &rt){
	if(!p[rt].l && !p[rt].r){ // 无左右子节点，删除本节点 
		rt = 0;
	}
	else if(!p[rt].l){ // 无左节点 
		p[rt].maxn = p[p[rt].r].maxn;
		p[rt].minn = p[p[rt].r].minn;
		p[rt].cnt = p[p[rt].r].cnt;
	} 
	else if(!p[rt].r){ // 无右节点 
		p[rt].maxn = p[p[rt].l].maxn;
		p[rt].minn = p[p[rt].l].minn;
		p[rt].cnt = p[p[rt].l].cnt;
	}
	else{ // 左右节点都存在  
		p[rt].maxn = max(p[p[rt].l].maxn,p[p[rt].r].maxn);
		p[rt].minn = min(p[p[rt].l].minn,p[p[rt].r].minn);
		p[rt].cnt = p[p[rt].l].cnt + p[p[rt].r].cnt;
	}
}

void update(int &rt,int l,int r,int pos,int val){
	if(!rt) rt = ++tot; // 动态开点 
	if(l == r && l == pos){ 
		p[rt].cnt += val; // val对应 +-1 表示插入或删除 
		if(p[rt].cnt > 0) // 本节点存在值 
			p[rt].maxn = p[rt].minn = l;
		else rt = 0; // 删除  
		return;
	}
	int m = l+r>>1;
	if(m >= pos) update(p[rt].l,l,m,pos,val);
	else update(p[rt].r,m+1,r,pos,val);
	push_up(rt);
}

int getRank(int L,int R,int l,int r,int rt){ // 其实就是求 [L,R] 存在的节点总和 
	if(!rt) return 0; // 不存在该节点 
	if(L <= l && r <= R){
		return p[rt].cnt;
	}
	int ans = 0;
	int m = l+r>>1;
	if(m >= L) ans += getRank(L,R,l,m,p[rt].l);
	if(m <  R) ans += getRank(L,R,m+1,r,p[rt].r);
	return ans;
}

int getFront(int L,int R,int l,int r,int rt){ // 就是求 [L,R] 最大值 
	if(!rt) return 0; // 不存在该节点 
	if(L <= l && r <= R){
		return p[rt].maxn;
	}
	int ans = 0;
	int m = l+r>>1;
	if(m >= L) ans = max(ans,getFront(L,R,l,m,p[rt].l)); 
	if(m <  R) ans = max(ans,getFront(L,R,m+1,r,p[rt].r));
	return ans;
}

int getLater(int L,int R,int l,int r,int rt){ //  就是求 [L,R] 最小值 
	if(!rt) return MAXN; // 不存在该节点 
	if(L <= l && r <= R){
		return p[rt].minn;
	}
	int ans = MAXN;
	int m = l+r>>1;
	if(m >= L) ans = min(ans,getLater(L,R,l,m,p[rt].l));
	if(m <  R) ans = min(ans,getLater(L,R,m+1,r,p[rt].r));
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	while(n--){
		int op,tar,rank;
		cin >> op >> tar;
		rank = tar;
		tar += 10000001; // [1,2e7+1]
		if(op == 1){
			update(root,1,MAXN,tar,1);
		}
		else if(op == 2){
			update(root,1,MAXN,tar,-1);
		}
		else if(op == 3){
			if(tar == 1) cout << 1 << "\n";
			else cout << getRank(1,tar-1,1,MAXN,root)+1 << "\n"; 
			
		}
		else if(op == 4){
			int l=1,r=20000001;
			int ans;
			while(l <= r){
				int mid = l+r>>1;
				int num = getRank(1,mid,1,MAXN,root);
				if(num >= rank) ans = mid ,r = mid-1;
				else l = mid+1;
			}
			cout << ans-10000001 << "\n";
		}
		else if(op == 5){
			int ans = getFront(1,tar-1,1,MAXN,root);
			cout << ans-10000001 << "\n";
		}
		else if(op == 6){
			int ans = getLater(tar+1,MAXN,1,MAXN,root);
			cout << ans-10000001 << "\n";
		}
	}
	

	return 0;
}
// 关于各函数调用： 
// rt位置，一定要填 root，而不是单纯的 1；
// 因为当一个数插入又删除导致整棵树为空后，再次插入时树根节点不再是 1 
// 相当于之前的空树都不要了； 
// root 始终指向线段树的根节点；
// 每一次树空了 root就会变化； 

/*
input： 
20
1 9508226
1 -9775935
2 9508226
2 -9775935
1 -6414629
3 -6414629
2 -6414629
1 -1847925
5 3248500
2 -1847925
1 -2757289
1 -7942063
1 -5545399
2 -7942063
1 6169408
5 -648755
1 -275474
1 -9836404
1 -3389358
1 -8467606

output：
1
-1847925
-2757289


*/
Prev
2021-04-11 18:42:00 # ACM
Next