【题目来源】
洛谷：[P2161 SHOI2009] 会场预约 - 洛谷
【题目描述】
PP 大厦有一间空的礼堂，可以为企业或者单位提供会议场地。
这些会议中的大多数都需要连续几天的时间（个别的可能只需要一天），不过场地只有一个，所以不同的会议的时间申请不能够冲突。也就是说，前一个会议的结束日期必须在后一个会议的开始日期之前。所以，如果要接受一个新的场地预约申请，就必须拒绝掉与这个申请相冲突的预约。
一般来说，如果 PP 大厦方面事先已经接受了一个会场预约（例如从 \(10\) 日到 \(15\) 日），就不会再接受与之相冲突的预约（例如从 \(12\) 日到 \(17\) 日）。
不过，有时出于经济利益，PP 大厦方面有时会为了接受一个新的会场预约，而拒绝掉一个甚至几个之前预订的预约。 于是，礼堂管理员 QQ 的笔记本上经常记录着这样的信息：（本题中为方便起见，所有的日期都用一个整数表示）例如，如果一个为期 \(10\) 天的会议从 \(90\) 日开始到 \(99\) 日，那么下一个会议最早只能在 \(100\) 日开始。（此处前后矛盾，若无法理解请参考形式化描述。）
最近，这个业务的工作量与日俱增，礼堂的管理员 QQ 希望参加 SHTSC 的你替他设计一套计算机系统，方便他的工作。这个系统应当能执行下面两个操作：
A 操作：有一个新的预约是从 \(start\) 日到 \(end\) 日，并且拒绝掉所有与它相冲突的预约。执行这个操作的时候，你的系统应当返回为了这个新预约而拒绝掉的预约个数，以方便 QQ 与自己的记录相校对。
B 操作：请你的系统返回当前的仍然有效的预约的总数。
形式化题意：
你需要维护一个在数轴上的线段的集合 \(S\)，支持两种操作：
A l r 表示将 \(S\) 中所有与线段 \([l,r]\) 相交的线段删去，并将 \([l,r]\) 加入 \(S\) 中。
B 查询 \(S\) 中的元素数量。
对于 A 操作，每次还需输出删掉的元素个数。
【输入】
第一行一个正整数 \(n\)，表示操作个数。
接下来 \(n\) 行，每行表示一个操作，都是上面两种中的一个。
【输出】
输出 \(n\) 行，每行一个整数，表示对应操作的答案。
【输入样例】
6
A 10 15
A 17 19
A 12 17
A 90 99
A 11 12
B
【输出样例】
0
0
2
0
1
2
【算法标签】
《洛谷 P2161 会场预约》 #平衡树# #树状数组# #各省省选# #2009# #上海#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 200005; // 最大数组大小int n; // 操作次数
int tr[N]; // 树状数组，用于统计区间覆盖
int ed[N]; // ed[i]：记录以i为左端点的区间的右端点
int tot; // 当前存在的区间总数/*** 计算lowbit：获取x的最低位的1* @param x 输入数值* @return x的最低位的1所代表的值*/
int lowbit(int x)
{return x & -x; // 利用补码性质
}/*** 树状数组单点更新操作* @param x 更新位置* @param c 增加的值*/
void add(int x, int c)
{// 树状数组标准更新操作，向上更新所有相关节点for (int i = x; i <= 100000; i += lowbit(i))tr[i] += c;
}/*** 树状数组前缀和查询操作* @param x 查询位置* @return 前x个位置的和*/
int query(int x)
{int res = 0;// 树状数组标准查询操作，向下累加所有相关节点for (int i = x; i; i -= lowbit(i))res += tr[i];return res;
}int main()
{// 输入操作次数cin >> n;// 处理n个操作for (int i = 1; i <= n; i++){char c;cin >> c; // 读入操作类型if (c == 'A') // 添加区间操作{int L, R, cnt = 0; // L,R: 区间端点, cnt: 被删除的区间数量cin >> L >> R;// 循环删除所有与新区间重叠的区间while (1){int l = 0, r = R; // 二分查找边界 [0, R]int ans; // 存储二分查找结果// 二分查找：找到最小的位置ans，使得query(ans) == query(R)// 这意味着区间[ans, R]内没有区间覆盖while (l <= r){int mid = (l + r) >> 1; // 计算中点if (query(mid) >= query(R)){ans = mid; // 记录当前位置r = mid - 1; // 继续向左查找更小的满足条件的位置}else {l = mid + 1; // 向右查找}}// 检查找到的区间是否与新区间重叠if (ed[ans] >= L) // 如果区间[ans, ed[ans]]与[L,R]重叠{add(ans, -1); // 从树状数组中删除该区间cnt++; // 被删除区间计数加1tot--; // 总区间数减1}else{break; // 没有重叠区间，退出循环}}// 输出被删除的区间数量cout << cnt << endl;// 添加新区间add(L, 1); // 在树状数组中标记新区间ed[L] = R; // 记录新区间的右端点tot++; // 总区间数加1}else // 查询操作：输出当前区间总数{cout << tot << endl;}}return 0;
}
【运行结果】
6
A 10 15
0
A 17 19
0
A 12 17
2
A 90 99
0
A 11 12
1
B
2