蒟蒻提供一种fhq-treap的做法，但是不如其他题解的快（也没有stl快，不开O2 1.8s），但是比较好想，扩展了fhq的模板，也算是为使用fhq提供一个新方法。
首先，fhq-treap是什么，如果有同学不清楚，请点击学习(并非我的blog)
那么，由于fhq树的分裂操作，使得我们可以很方便的取出我们想要的区间。
那么，在这道题里，我们想要的区间是什么呢？
首先，对于B操作，我们只需要维护一个cnt，让他每次减掉删除的数量再加1就好了，这很容易。
但是，对于一次A x操作，我们需要找到所有与x区间重合的区间进行删除，删除好说，那怎么找呢？
我们这里改动一下传统fhq的模板，让存储的“关键码”val变成区间（以下代码中的node型）
struct FHQ_Treap{
int l,r;
int dat,siz;
node val;
}t[N];
然后定义node的比较操作：
- 区间x==区间y，当且仅当x，y有重叠部分
- 区间x<区间y，当且仅当x在y左边并且没有重叠，即x的右端点小于y的左端点
- 区间x<=区间y，当且仅当x==y或x<y
代码如下：
struct node{
int l,r;
bool operator==(const node &o)const{
return (l<=o.r&&o.r<=r)||(l<=o.l&&o.l<=r)||(o.l<=r&&r<=o.r)||(o.l<=l&&l<=o.r);
}
bool operator<(const node &o)const{
return (r<o.l);
}
bool operator<=(const node &o)const{
return (*this)<o||(*this)==o;
}
};
现在，我们把模板复制过来，改一下变量类型，然后你就会发现，过不了样例！
原因是啥呢？试想如果有两个区间\(x=[1,4]\),\(y=[7,9]\),现在插入区间\(i=[2,8]\)
那么就只会删除其中一个，因为x与y没有重合，换句话说!(x==y),（注意不能写成x！=y）。
那咋办呢？
我们发现，虽然!(x==y),但是x==i且y==i，那么我们先插入一次i，那么就可以将x和y“连起来”，让他们一起被删除。
所以我们只要先插入一次i再删除就好啦
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
struct node{
int l,r;
bool operator==(const node &o)const{
return (l<=o.r&&o.r<=r)||(l<=o.l&&o.l<=r)||(o.l<=r&&r<=o.r)||(o.l<=l&&l<=o.r);
}
bool operator<(const node &o)const{
return (r<o.l);
}
bool operator<=(const node &o)const{
return (*this)<o||(*this)==o;
}
};
class FTreap{
public:
struct FHQ_Treap{
int l,r;
int dat,siz;
node val;
}t[N];
#define l(p) t[p].l
#define r(p) t[p].r
#define dat(p) t[p].dat
#define val(p) t[p].val
#define siz(p) t[p].siz
int tot;
int New(node val){
int np=++tot;
val(np)=val;
dat(np)=rand();
siz(np)=1;
return np;
}
void Pushup(int p){
siz(p)=siz(l(p))+siz(r(p))+1;
}
int root;const int INF=INT_MAX;
void SplitByVal(int p,int &x,int &y,node val)
{
if(!p){
x=y=0;
return;
}
if(val(p)<=val){
x=p,SplitByVal(r(p),r(x),y,val);
}else{
y=p,SplitByVal(l(p),x,l(y),val);
}
Pushup(p);//分裂后,p的左或右子树已经改变
}
void SplitByVal2(int p,int &x,int &y,node val)
{
if(!p){
x=y=0;
return;
}
if(val(p)<val){
x=p,SplitByVal2(r(p),r(x),y,val);
}else{
y=p,SplitByVal2(l(p),x,l(y),val);
}
Pushup(p);//分裂后,p的左或右子树已经改变
}
int Merge(int x,int y){//返回合并后的root
if(!x||!y) return x+y;//有一子树不存在,直接合并
if(dat(x)<dat(y)){//按照大根堆性质合并 (确定上下关系)
l(y)=Merge(x,l(y));//注意我们不能把参数传反了
Pushup(y);
return y;
}else{
r(x)=Merge(r(x),y);
Pushup(x);
return x;
}
}
int Insert(node val){
int t1=0,t2=0,t3=0;
SplitByVal(root,t1,t2,val);
int tt1=Merge(t1,New(val));
root=Merge(tt1,t2);
t1=0,t2=0,t3=0;
SplitByVal(root,t1,t2,val);
SplitByVal2(t1,t1,t3,val);
int ret=siz(t3)-1;//注意这里不包括我们之前插进去的那个，所以要-1
root=Merge(Merge(t1,New(val)),t2);
return ret;
}
}tr;
int n;
int main(){
cin>>n;
int cnt=0;
while(n--){
char op;int l,r;
cin>>op;
if(op=='A'){
cin>>l>>r;
int res=tr.Insert({l,r});
cnt-=res;cnt++;
cout<<res<<endl;
}else cout<<cnt<<endl;
}
}