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

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

struct node{

    node* ch[],*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[]=ch[]=prt=;

        typ=;sz=;Maxlen=r-l+;Maxpos=l;

    }

    node(int x){//black

        l=r=x;sz=;typ=;Maxlen=Maxpos=;ch[]=ch[]=prt=;

    }

    void update(){

        sz=typ;

        if(ch[])sz+=ch[]->sz;

        if(ch[])sz+=ch[]->sz;

        if(typ==){

            Maxlen=r-l+;Maxpos=l;

        }else{

            Maxlen=Maxpos=;

        }

        if(ch[]){

            if(ch[]->Maxlen>Maxlen){

                Maxlen=ch[]->Maxlen;Maxpos=ch[]->Maxpos;

            }

        }

        if(ch[]){

            if(ch[]->Maxlen>=Maxlen){

                Maxlen=ch[]->Maxlen;Maxpos=ch[]->Maxpos;

            }

        }

    }

}t[maxn*];int tot=;

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[],pos);

    if(pos<rt->l)return findpos(rt->ch[],pos);

}

inline int isch1(node* rt){return rt==rt->prt->ch[];}

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^];

    if(c->ch[t^])c->ch[t^]->prt=rt;

    c->ch[t^]=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!=){

      rot(p,isch1(rt),root);

    }

}

void split(int l,int r){//l,r:ordinate

    splay(findpos(root,l),root);

    c0=root->ch[];

    if(c0){

        root->ch[]=;c0->prt=;root->update();

    }

    splay(findpos(root,r),root);

    c1=root->ch[];

    if(c1){

        root->ch[]=;c1->prt=;root->update();

    }

}

node* leftmost(node* rt){

    if(rt->ch[])return leftmost(rt->ch[]);

    else return rt;

}

node* rightmost(node* rt){

    if(rt->ch[])return rightmost(rt->ch[]);

    else return rt;

}

void merge(){

    if(c0){

        splay(leftmost(root),root);

        root->ch[]=c0;c0->prt=root;root->update();

    }

    if(c1){

        splay(rightmost(root),root);

        root->ch[]=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==){

            root->ch[]=c0;c0->prt=root;root->update();c0=;

        }else{

            c0->r=root->r;c0->prt=;root=c0;root->update();c0=;

        }

    }

     if(c1){

       splay(leftmost(c1),c1);

       if(c1->typ==){

            root->ch[]=c1;c1->prt=root;root->update();c1=;

       }else{//printf("!");printf("%d\n",leftmost(root)->l);

            c1->l=root->l;c1->ch[]=root->ch[];

            if(root->ch[])root->ch[]->prt=c1;

            c1->prt=;

            root=c1;root->update();c1=;

        }

    }

}

int Add(){

    int pos=root->Maxpos+root->Maxlen/;

    split(pos,pos);

    if(pos>root->l){

        root->ch[]=newnode(root->l,pos-);root->ch[]->prt=root;

    }

    if(pos<root->r){

        root->ch[]=newnode(pos+,root->r);root->ch[]->prt=root;

    }

    root->typ=;root->sz=;root->l=root->r=pos;root->Maxlen=root->Maxpos=;

    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(,n);

    for(int i=;i<=q;++i){

        scanf("%d",&K[i]);

        if(K[i]==)scanf("%d%d",&L[i],&R[i]);

        else seq[++cnt]=i;

    }

    sort(seq+,seq+cnt+,cmp);

    int old=-,tot=;//discrete to [0,...

    for(int i=;i<=cnt;++i){

        if(old!=K[seq[i]]){

            old=K[seq[i]];++tot;

        }

        K[seq[i]]=tot;

    }

    for(int i=;i<=q;++i){

        if(K[i]==){

            query(L[i],R[i]);

        }else{

            if(pos[K[i]]==){

                pos[K[i]]=Add();

            }else{

                Remove(pos[K[i]]);pos[K[i]]=;

            }

        }

    }

    return ;

}