《P2161 [SHOI2009] 会场预约》
题目背景
形式化描述
你需要维护一个在数轴上的线段的集合 S，支持两种操作：
A l r 表示将 S 中所有与线段 [l,r] 相交的线段删去，并将 [l,r] 加入 S 中。
B 查询 S 中的元素数量。
对于 A 操作，每次还需输出删掉的元素个数。
题目描述
PP 大厦有一间空的礼堂，可以为企业或者单位提供会议场地。
这些会议中的大多数都需要连续几天的时间（个别的可能只需要一天），不过场地只有一个，所以不同的会议的时间申请不能够冲突。也就是说，前一个会议的结束日期必须在后一个会议的开始日期之前。所以，如果要接受一个新的场地预约申请，就必须拒绝掉与这个申请相冲突的预约。
一般来说，如果 PP 大厦方面事先已经接受了一个会场预约（例如从 10 日到 15 日），就不会再接受与之相冲突的预约（例如从 12 日到 17 日）。
不过，有时出于经济利益，PP 大厦方面有时会为了接受一个新的会场预约，而拒绝掉一个甚至几个之前预订的预约。 于是，礼堂管理员 QQ 的笔记本上经常记录着这样的信息：（本题中为方便起见，所有的日期都用一个整数表示）例如，如果一个为期 10 天的会议从 90 日开始到 99 日，那么下一个会议最早只能在 100 日开始。（此处前后矛盾，若无法理解请参考形式化描述。）
最近，这个业务的工作量与日俱增，礼堂的管理员 QQ 希望参加 SHTSC 的你替他设计一套计算机系统，方便他的工作。这个系统应当能执行下面两个操作：
A 操作：有一个新的预约是从 start 日到 end 日，并且拒绝掉所有与它相冲突的预约。执行这个操作的时候，你的系统应当返回为了这个新预约而拒绝掉的预约个数，以方便 QQ 与自己的记录相校对。
B 操作：请你的系统返回当前的仍然有效的预约的总数。
输入格式
第一行一个正整数 n，表示操作个数。
接下来 n 行，每行表示一个操作，都是上面两种中的一个。
输出格式
输出 n 行，每行一个整数，表示对应操作的答案。
输入输出样例
输入 #1复制
6 A 10 15 A 17 19 A 12 17 A 90 99 A 11 12 B
输出 #1复制
0 0 2 0 1 2
说明/提示
【数据范围】
对于 100% 的数据，1≤n≤2×105，1≤l≤r≤105。
代码实现：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
struct Reservation {
int start, end;
bool operator <(const Reservation &other) const {
return end < other.start;
}
};
int queryCount;
set<Reservation> reservationSet;
int main() {
cin >> queryCount;
while (queryCount--) {
char operation;
scanf(" %c", &operation); // 空格用于跳过空白字符
if (operation == 'A') {
int startTime, endTime, conflictCount = 0;
scanf("%d %d", &startTime, &endTime);
Reservation newItem = {startTime, endTime};
// 删除冲突的预约并统计数量
set<Reservation>::iterator it = reservationSet.find(newItem);
while (it != reservationSet.end()) {
++conflictCount;
reservationSet.erase(it);
it = reservationSet.find(newItem);
}
reservationSet.insert(newItem);
printf("%d\n", conflictCount);
}
else {
printf("%d\n", reservationSet.size());
}
}
return 0;
}