2021.12.08 [SHOI2009]会场预约（平衡树游码表）
https://www.luogu.com.cn/problem/P2161
题意：
你需要维护一个 在数轴上的线段 的集合 \(S\)，支持两种操作：
A l r 表示将 \(S\) 中所有与线段 \([l,r]\) 相交的线段删去，并将 \([l,r]\) 加入 \(S\) 中。
B 查询 \(S\) 中的元素数量。
对于 A 操作，每次还需输出删掉的元素个数。
分析：
对于这道题，我先想到了珂朵莉树（毕竟这个名字太深入人心，虽然实际就是游码表），然后发现……坏了，忘了怎么打了，于是转战平衡树。
把FHQ Treap存的关键码变成俩，一个存 \(l\) ，一个存 \(r\) 。
对于操作A：首先按照 \(l\) ，以 \(l+1\) 为标准，分离出 \([1,l]\) 与 \([l+1,n]\) ，然后再按照 \(r\) ，以 \(r\) 为标准，分离出 \([1,r-1]\) 与 \([r,n]\) ，对于中间部分输出大小，加入新点，合并。
对于操作B：输出平衡树总大小。
代码如下：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
int n,root,cnt,sizei[N],son[N][2],val[N][2],key[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline int add(int x,int y){
++cnt;
sizei[cnt]=1;
val[cnt][0]=x;val[cnt][1]=y;
key[cnt]=rand();
return cnt;
}
inline void update(int x){
sizei[x]=sizei[son[x][0]]+sizei[son[x][1]]+1;
}
inline void split(int rt,int k,int flag,int &x,int &y){
if(!rt)return (void)(x=y=0);
if(val[rt][flag]<k)
x=rt,split(son[rt][1],k,flag,son[rt][1],y);
else y=rt,split(son[rt][0],k,flag,x,son[rt][0]);
update(rt);
}
inline int merge(int x,int y){
if(!x||!y)return x+y;
if(key[x]>=key[y]){
son[x][1]=merge(son[x][1],y);
update(x);
return x;
}else{
son[y][0]=merge(x,son[y][0]);
update(y);
return y;
}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
char ch;
cin>>ch;
if(ch=='A'){
int u,v;
u=read();v=read();
int x,y,z;
split(root,v+1,0,x,z);
split(x,u,1,x,y);
cout<<sizei[y]<<endl;
root=merge(merge(x,add(u,v)),z);
}else cout<<sizei[root]<<endl;
}
return 0;
}
