这一题据说被放在了线段树这个模块下面。
我想了很久很久。想到了一种做法。但是一写就感觉很麻。
想着想着，算了一下复杂度，然后大喊一声，MADE！
仔细一想，询问2E5，值域1E5。大力上分块啊，\(O(Nsqrt(M))\approx 6E7\)不满。搞什么线段树啊，真是的。
好的，那么大力上分块。
具体应该要怎么分块呢？
对于每一块，我们定义一种标记。
如果标记是0，说明这个块是空的，那么就可以直接修改；
如果标记是一个正整数，说明这个块被该正整数完全包含，也可以直接修改，并将该标记指的数放入删除集合；
如果标记是-1，说明这个块里面包含多个询问。此时同样暴力修改。
为什么这样做的复杂度是对的呢？首先，如果一个块，如果它包含多个询问，那么要么它包含的是整个询问，要么它包含的是询问的一段。
因此，对于一个询问，它最多只可能被暴力修改两次。
所以这种做法是可行的。
不过分块写起来还是挺麻的。调了半天没调出来，然后看到了一个神仙做法，就抄过来了：
具体来说，就是把Set当作红黑树用。
太猛了。
#include<cmath>
#include
#include
#include<cstring>
#include<set>
using namespace std;
#define MAXN 100000
int n;
struct data{
int l,r;
bool operator <(const data &A)const{
return (this->l==A.l)?(this->l<A.r):(this->l<A.l);
}
};
set<data> st;
void init(){
scanf("%d",&n);
char ch[5];
int l,r,ans;
for(int i=1;i<=n;++i){
cin>>ch;
if(ch[0]=='B'){
printf("%lld\n",st.size());
}else{
scanf("%d%d",&l,&r);
data X=(data){l,r};
ans=0;
set<data>::iterator it=st.lower_bound(X);
while(1){
it=st.lower_bound(X);
if(it->l<=X.r&&X.l<=it->r){
++ans;
st.erase(it);
continue;
}
it=st.lower_bound(X);
if(it!=st.begin()){
--it;
if(it->l<=X.r&&X.l<=it->r){
++ans;
st.erase(it);
continue;
}
}
break;
}
st.insert(X);
printf("%d\n",ans);
}
}
}
int main(){
init();
return 0;
}
//大力分块的假做法，直到现在都不懂bug在哪里。第k块表示k*blck~(k+1)*blck-1的值。
int n,cnt=0,blck,L[200005],R[200005],rst,TOP;
int V[317],v[100005];
char ch[4];
bool bo[200005];
inline void prpr(){
blck=sqrt(MAXN);
rst=MAXN%blck;
TOP=MAXN-rst;
memset(V,0,sizeof(V));
memset(v,0,sizeof(v));
memset(bo,0,sizeof(bo));
}
int rt=0;
inline void delB(const int &l,const int &r,const int &x){
for(int i=l;i<=r;++i){
if(V[i]==x){
V[i]=0;
}
}
}
inline void delb(const int &l,const int &r,const int &x){
for(int i=l;i<=r;++i){
if(v[i]==x){
v[i]=0;
}
}
}
inline void del(const int &x){
bo[x]=0;
++rt;--cnt;
int l=L[x],r=R[x];
if(r/blck-1<(l/blck+1)){
delb(l,r,x);
return;
}
delB(l/blck+1,r/blck-1,x);
delb(l,(l/blck+1)*blck-1,x),delb((r/blck)*blck,r,x);
}
inline void addb(const int &l,const int &r,const int &x){
for(int i=l;i<=r;++i){
if(V[i/blck]!=x){
V[i/blck]=-1;
}
if(!bo[v[i]]){
v[i]=x;
}else{
del(v[i]);
v[i]=x;
}
}
}
inline void clr(const int &x){
for(int i=x*blck;i<(x+1)*blck;++i){
if(bo[v[i]]){
del(v[i]);
}
}
}
inline void addB(const int &l,const int &r,const int &x){
for(int i=l;i<=r;++i){
if(!V[i]){
V[i]=x;
}else if(V[i]>0){
if(bo[V[i]]){
del(V[i]);
}
V[i]=x;
}else{
clr(i);
V[i]=x;
}
}
}
inline int add(const int &l,const int &r,const int &x){
rt=0;
if(r/blck-1<(l/blck+1)){
addb(l,r,x);
return rt;
}
addB(l/blck+1,r/blck-1,x);
addb(l,(l/blck+1)*blck-1,x),addb((r/blck)*blck,r,x);
return rt;
}
void init(){
prpr();
scanf("%d",&n);
int l,r;
for(int i=1;i<=n;++i){
cin>>ch;
if(ch[0]=='B'){
printf("%d\n",cnt);
}else{
bo[i]=1;++cnt;
scanf("%d%d",&l,&r);
printf("%d\n",add(l-1,r-1,i));
L[i]=l-1,R[i]=r-1;
}
}
}
int main(){
init();
return 0;
}