题意：小 M 的实验室有很多电源插排。这些插排的编号从 1 到 N，由左向右排成一排。
每天早晨，这些插排都是没有被使用的。每当一个学生来到实验室，他就将自己的笔记本电源插到某一个未被使用的插排上。实验室的同学们都很奇怪，他们完成这个过程是这样的：首先，他们找到还没有被使用的插排的最长区间。如果有多个区间长度相同，他们就选择最靠右的那个。然后将自己的电源插到该区间的中间。如果区间长度是偶数，他们同样选择靠右的那个。当一个同学离开实验室时，他会将自己的电源拔出来。数据保证每一个同学来到实验室时，至少有一个空的插排。
现在给你实验室同学的来到和离开事件，和一些询问。对于每一个询问，你需要计算在区间 [L,R] 已经有多少个插排被使用了。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
struct node{
    node* ch[2],*prt;
    int typ,l,r;
    int sz;//number of black nodes
    int Maxlen,Maxpos;
    node(){}
    node(int _l,int _r){//white interval (include l==r)
        l=_l;r=_r;ch[0]=ch[1]=prt=0;
        typ=0;sz=0;Maxlen=r-l+1;Maxpos=l;
    }
    node(int x){//black
        l=r=x;sz=1;typ=1;Maxlen=Maxpos=0;ch[0]=ch[1]=prt=0;
    }
    void update(){
        sz=typ;
        if(ch[0])sz+=ch[0]->sz;
        if(ch[1])sz+=ch[1]->sz;
        if(typ==0){
            Maxlen=r-l+1;Maxpos=l;
        }else{
            Maxlen=Maxpos=0;
        }
        if(ch[0]){
            if(ch[0]->Maxlen>Maxlen){
                Maxlen=ch[0]->Maxlen;Maxpos=ch[0]->Maxpos;
            }
        }
        if(ch[1]){
            if(ch[1]->Maxlen>=Maxlen){
                Maxlen=ch[1]->Maxlen;Maxpos=ch[1]->Maxpos;
            }
        }
    }
}t[maxn*4];int tot=0;
node* newnode(int l,int r){
    t[++tot]=node(l,r);return t+tot;
}
node* newnode(int x){
    t[++tot]=node(x);return t+tot;
}
node *root,*c0,*c1;
node* findpos(node* rt,int pos){//ordinate assert:pos exist
    if(rt->l<=pos&&pos<=rt->r)return rt;
    if(pos>rt->r)return findpos(rt->ch[1],pos);
    if(pos<rt->l)return findpos(rt->ch[0],pos);
}
inline int isch1(node* rt){return rt==rt->prt->ch[1];}
void rot(node* rt,int t,node* &root){
    node* p=rt->prt,*c=rt->ch[t];
    if(!p)root=c;
    else p->ch[isch1(rt)]=c;
    c->prt=p;
    rt->ch[t]=c->ch[t^1];
    if(c->ch[t^1])c->ch[t^1]->prt=rt;
    c->ch[t^1]=rt;rt->prt=c;
    rt->update();c->update();
}
void splay(node* rt,node* &root){
    node *p,*g;
    while((p=rt->prt)&&(g=p->prt)){
        int t1=isch1(rt),t2=isch1(p);
        if(t1==t2){rot(g,t2,root);rot(p,t1,root);}
        else {rot(p,t1,root);rot(g,t2,root);}
    }
    if(p!=0){
      rot(p,isch1(rt),root);
    }
}
void split(int l,int r){//l,r:ordinate
    splay(findpos(root,l),root);
    c0=root->ch[0];
    if(c0){
        root->ch[0]=0;c0->prt=0;root->update();
    }
    splay(findpos(root,r),root);
    c1=root->ch[1];
    if(c1){
        root->ch[1]=0;c1->prt=0;root->update();
    }
}
node* leftmost(node* rt){
    if(rt->ch[0])return leftmost(rt->ch[0]);
    else return rt;
}
node* rightmost(node* rt){
    if(rt->ch[1])return rightmost(rt->ch[1]);
    else return rt;
} 
void merge(){
    if(c0){
        splay(leftmost(root),root);
        root->ch[0]=c0;c0->prt=root;root->update();
    }
    if(c1){
        splay(rightmost(root),root);
        root->ch[1]=c1;c1->prt=root;root->update();
    }
}
void query(int l,int r){
    split(l,r);
    printf("%d\n",root->sz);
    merge();
}
void Remove(int pos){
   
    split(pos,pos);root=newnode(pos,pos);
    if(c0){
        splay(rightmost(c0),c0);
        if(c0->typ==1){
            root->ch[0]=c0;c0->prt=root;root->update();c0=0;
        }else{
            c0->r=root->r;c0->prt=0;root=c0;root->update();c0=0;
        }
    }
     if(c1){
       splay(leftmost(c1),c1);
       if(c1->typ==1){
            root->ch[1]=c1;c1->prt=root;root->update();c1=0;
       }else{//printf("!");printf("%d\n",leftmost(root)->l);
            c1->l=root->l;c1->ch[0]=root->ch[0];
            if(root->ch[0])root->ch[0]->prt=c1;
            c1->prt=0;
            root=c1;root->update();c1=0;
        }
    }
}
int Add(){
    int pos=root->Maxpos+root->Maxlen/2;
    split(pos,pos);
    if(pos>root->l){
        root->ch[0]=newnode(root->l,pos-1);root->ch[0]->prt=root;
    
    }
    if(pos<root->r){
        root->ch[1]=newnode(pos+1,root->r);root->ch[1]->prt=root;
    }
    root->typ=1;root->sz=1;root->l=root->r=pos;root->Maxlen=root->Maxpos=0;
    root->update();
    merge();
    return pos;
}
int n,q;
int pos[maxn];
int L[maxn],R[maxn],K[maxn],seq[maxn],cnt;
bool cmp(const int &a,const int &b){
    return K[a]<K[b];
}
int main(){
    scanf("%d%d",&n,&q);
    root=newnode(1,n);
    for(int i=1;i<=q;++i){
        scanf("%d",&K[i]);
        if(K[i]==0)scanf("%d%d",&L[i],&R[i]);
        else seq[++cnt]=i;
    }
    sort(seq+1,seq+cnt+1,cmp);
    int old=-1,tot=0;//discrete to [0,...
    for(int i=1;i<=cnt;++i){
        if(old!=K[seq[i]]){
            old=K[seq[i]];++tot;
        }
        K[seq[i]]=tot;
    }
    for(int i=1;i<=q;++i){
        if(K[i]==0){
            query(L[i],R[i]);
        }else{
            if(pos[K[i]]==0){
                pos[K[i]]=Add();
            }else{
                Remove(pos[K[i]]);pos[K[i]]=0;
            }
        }
    }
    return 0;
}