HihoCoder1325 (Splay)[STL]

发表于 | 更新于 | | 阅读次数：

题目链接：https://hihocoder.com/problemset/problem/1329

Splay模板题，这里记录用set的lower_bound、upper_bound和erase的区间删除功能实现的做法。

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
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
char str[10];
int n;
set<int> s;
int main() {
	int k;
	int a,b;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%s",str);
		if(str[0]=='I') {
			scanf("%d",&k);
			s.insert(k);
		}
		else if(str[0]=='Q') {
			scanf("%d",&k);
			set<int>::iterator it;
			it=s.upper_bound(k);
			it--;
			printf("%d\n",(*it));
		}
		else if(str[0]=='D') {
			scanf("%d%d",&a,&b);
			set<int>::iterator it1;
			set<int>::iterator it2;
			it1=s.lower_bound(a);
			it2=s.upper_bound(b);
			s.erase(it1,it2);
		}
	}
}