没事打了个Splay，然后调了3h。
觉得题解的找前驱后继与删除复杂了点，主要讲一下这的思路。
由于平衡树中每一个点代表的区间互不相交，所有平衡树满足 \(l,r\) 两个值的BST。
以 \(l\) 为第一关键字排序，其他操作同Splay。
找后继的时候插入一个 \((r,r)\) 的点，然后旋转至顶端，找到自己的右儿子的最左边。
记得要删除 \((r,r)\)。
剩下的就是求前驱了，求前驱仍然插入一个 \((l,l)\) 的点，但此时如果只找左儿子的最右边会出问题，因为求前驱时要求的是满足最大的 \(r_i < l\)，所以有可能不满足条件，那么将分情况讨论。
1、无左儿子，为父亲节点。
2、有左儿子，为左儿子的最右边。
分情况讨论即可。
理论复杂度为 \(O(n)\),但实际上便历过的点都是要删的，所以复杂度不高。
最后将前驱延展到根节点，后继延展到根节点的右儿子，删除后继的左儿子即可，即赋值为 \(0\)。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=6e5+5;
int n,cnt,root;
struct node
{
int fa,ch[2],x,y,cnt,siz;
}t[N];
inline void newnode(int &x,int fa,int wx,int wy)
{
x=++cnt;
t[x].fa=fa;
t[x].x=wx;
t[x].y=wy;
t[x].cnt=t[x].siz=1;
}
inline void connect(int x,int fa,int son)
{
t[x].fa=fa;
t[fa].ch[son]=x;
}
inline bool ident(int x,int fa)
{
return t[fa].ch[1]==x;
}
inline void pushup(int x)
{
t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].cnt;
}
inline void rotate(int x)
{
int fa=t[x].fa,ff=t[fa].fa,k=ident(x,fa);
connect(t[x].ch[k^1],fa,k);
connect(fa,x,k^1);
connect(x,ff,ident(fa,ff));
pushup(fa),pushup(x);
}
void splay(int x,int topp=0)
{
if(topp==0)root=x;
while(t[x].fa!=topp)
{
int fa=t[x].fa,ff=t[fa].fa;
if(ff!=topp)ident(x,fa)^ident(fa,ff)?rotate(x):rotate(fa);
rotate(x);
}
}
void insert(int wx,int wy,int &x=root,int fa=0)
{
if(!x)newnode(x,fa,wx,wy),splay(x);
else if(t[x].x==wx&&t[x].y==wy)t[x].cnt++,splay(x);
else if(t[x].x>wx)insert(wx,wy,t[x].ch[0],x);
else insert(wx,wy,t[x].ch[1],x);
}
void erase(int x=root)
{
if(t[x].cnt>1)t[x].cnt--;
else if(t[x].ch[1])
{
int p=t[x].ch[1];
while(t[p].ch[0])p=t[p].ch[0];
splay(p,x),t[p].fa=0,root=p,connect(t[x].ch[0],p,0);
pushup(p);
}
else root=t[x].ch[0],t[root].fa=0;
}
int pre(int val)
{
insert(val,val);
int p=t[root].ch[0];
while(t[p].ch[1])p=t[p].ch[1];
if(t[p].y>=val)
{
if(t[p].ch[0])
{
p=t[p].ch[0];
while(t[p].ch[1])p=t[p].ch[1];
}
else p=t[p].fa;
}
int res=p;
erase();
return res;
}
int suf(int val)
{
insert(val,val);
int p=t[root].ch[1];
while(t[p].ch[0])p=t[p].ch[0];
int res=p;
erase();
return res;
}
int del(int l,int r)
{
int x=pre(l),y=suf(r);
splay(x);
splay(y,x);
int ans=t[t[y].ch[0]].siz;
t[y].ch[0]=0;
pushup(y),pushup(x);
return ans;
}
int main()
{
insert(0,0);
insert(1e9,1e9);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
char opt;
scanf("%c",&opt);
while(opt!='A'&&opt!='B')scanf("%c",&opt);
if(opt=='A')
{
int l,r;
scanf("%d%d",&l,&r);
int ans=del(l,r);
insert(l,r);
printf("%d\n",ans);
}
if(opt=='B')
{
int ans=t[root].siz-2;
printf("%d\n",ans);
}
}
return 0;
}