题意：支持操作：
按顺序在数轴上插入一条线段，删除并询问所有与这条线段有交的线段个数。
询问当前数轴上一共有多少条线段。
Solution
想做了很久的题=。=
观察到和线段\([l_i,r_i]\)有交的线段，实际上就是右端点\(\ge l_i\)并且左端点\(\le r_i\) 的一些线段。我们可以把所有线段按照右端点第一关键字，左端点第二关键字放进一个Treap里。然后每次查询当前插入的这条线段的后继，即第一个右端点\(\ge l_i\)的线段。如果它们有交，就删掉这个线段，然后继续判断，否则\(break\)掉就行了。
Code
#include<set>
#include<map>
#include<queue>
#include<cctype>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using std::min;
using std::max;
using std::swap;
typedef double db;
const int N=200005;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define mp(A,B) std::make_pair(A,B)
int l[N],r[N];
int n,tot,root;
int ch[N][2],sze[N];
int prio[N],val[N],id[N];
void pushup(int cur){
sze[cur]=sze[ch[cur][0]]+sze[ch[cur][1]]+1;
}
void rotate(int &cur,int d){
int x=ch[cur][d],y=ch[x][d^1];
ch[cur][d]=y;ch[x][d^1]=cur;
pushup(cur);pushup(x);cur=x;
}
void insert(int &cur,int x,int idx){
if(!cur){
cur=++tot;
val[cur]=x;id[cur]=idx;
sze[cur]=1;prio[cur]=rand();return;
} sze[cur]++;
int d=val[cur]<x or val[cur]==x and l[id[cur]]<l[idx];
insert(ch[cur][d],x,idx);
if(prio[ch[cur][d]]<prio[cur]) rotate(cur,d);
}
void remove(int &cur,int x,int idx){
if(val[cur]==x){
if(!ch[cur][0] or !ch[cur][1]){
cur=ch[cur][0]+ch[cur][1];
return;
} if(prio[ch[cur][0]]<prio[ch[cur][1]])
rotate(cur,0),remove(ch[cur][1],x,idx);
else rotate(cur,1),remove(ch[cur][0],x,idx);
pushup(cur);return;
}
int d=val[cur]<x or val[cur]==x and l[id[cur]]<l[idx];
remove(ch[cur][d],x,idx);
pushup(cur);
}
const int inf=0x3f3f3f3f;
int nxt(int cur,int x){
if(!cur) return inf;
if(val[cur]<x) return nxt(ch[cur][1],x);
int p=nxt(ch[cur][0],x);
if(p!=inf) return p;
return id[cur];
}
int getint(){
int X=0,w=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while( isdigit(ch))X=X*10+ch-48,ch=getchar();
if(w) return -X;return X;
}
signed main(){
srand(20020619);
n=getint();
for(int i=1;i<=n;i++){
char ch[10];scanf("%s",ch);
if(ch[0]=='A'){
l[i]=getint(),r[i]=getint();
int p=nxt(root,l[i]),tot=0;
while(p!=inf and l[p]<=r[i]){
// printf("p=%d\n",p);
remove(root,r[p],p);
p=nxt(root,l[i]);tot++;
}
insert(root,r[i],i);
printf("%d\n",tot);
} else
printf("%d\n",sze[root]);
} return 0;
}
