Bzoj 2028(平衡树/Set)

BZOJ 2028
luogu免权限地址
Set维护不相交区间,lower_bound求前后与当前区间最近的区间,检查是否重合,重合即删除,直到不重合为止。
注意set.lower_bound()如果找不到就会返回set.end()

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
struct data {
int l, r;
bool operator < (const data &b) const {
if (l == b.l) return r < b.r;
return l < b.l;
}
};
set<data> s;
int n;
int getch() {
char ch = getchar();
while (ch != 'A' && ch != 'B') ch = getchar();
return ch == 'A' ? 1 : 2;
}
void clean() {}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
int opt = getch();
if (opt == 2) printf("%d\n", (int)s.size()); else {
int ans = 0;
int l, r;
scanf("%d%d", &l, &r);
data a = (data){l, r};
while (true) {
set<data>::iterator p = s.lower_bound(a);
if (p->l <= r && p->r >= l) {
ans++;
s.erase(p);
continue;
}
p = s.lower_bound(a);
if (p != s.begin()) {
p--;
if (p->l <= r && p->r >= l) {
ans++;
s.erase(p);
continue;
}
}
s.insert(a);
printf("%d\n", ans);
break;
}
}
}
}
int main() {
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------