描述 小 M 的实验室有很多电源插排。这些插排的编号从 1 到 N，由左向右排成一排。
每天早晨，这些插排都是没有被使用的。每当一个学生来到实验室，他就将自己的笔记本电源插到某一个未被使用的插排上。实验室的同学们都很奇怪，他们完成这个过程是这样的：首先，他们找到还没有被使用的插排的最长区间。如果有多个区间长度相同，他们就选择最靠右的那个。然后将自己的电源插到该区间的中间。如果区间长度是偶数，他们同样选择靠右的那个。当一个同学离开实验室时，他会将自己的电源拔出来。数据保证每一个同学来到实验室时，至少有一个空的插排。
现在给你实验室同学的来到和离开事件，和一些询问。对于每一个询问，你需要计算在区间 [L,R] 已经有多少个插排被使用了。
格式 输入格式 第一行是两个整数 N 和 Q，表示插排数量和询问数量。接下来 Q 行，每一行以一个整数 K 开头，如果 K 为 0，接下来就是两个整数 L 和 R(1 ≤ L ≤ R ≤ N)，表示一个询问。否则表示编号为 K 的学生到来或离开 (K ≤ 109)。K 的奇数次出现表示到来，偶数次出现表示离开。每个学生的编号都是唯一的。
输出格式 对于每一个询问，输出一个整数，表示询问区间内有多少个插排已经被使用了。
样例1 样例输入1 7 10
1
2
3
0 1 2
0 4 7
0 2 5
20
0 6 6
99
0 4 6
样例输出1 1
2
2
1
3
限制 对于 30% 的数据，N ≤ 10^510
​5
​​ ,Q ≤ 10^310
​3
​​
对于 100% 的数据，N ≤ 10^910
​9
​​ ,Q ≤ 10^510
​5
​​ 分析:一开始就失了智，，直接splay爆上，以为直接能过，结果拍惨了。。最后连样例都过不了，坚持不打指针，最后不得不屈服，不然变量都搞混了，我也是蠢得没谁了。
题解是STL大法好+线段树维护，感觉一脸很复杂不可做的样子。 #include #include #include //#include #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=3e5+5; int loc[N],n,m,q; int left[N],right[N],pos[N],a[N],cnt; bool cmp(const int &a,const int &b) { return pos[a]<pos[b]; } struct data{ data* ss[2],*pointt; int kindd,l,r; int cntt; int lenmx,locmx; data(){} data(int _l,int _r){ l=_l;r=_r;ss[0]=ss[1]=pointt=0; kindd=0;cntt=0;lenmx=r-l+1;locmx=l; } data(int x){ l=r=x;cntt=1;kindd=1;lenmx=locmx=0;ss[0]=ss[1]=pointt=0; } void up(){ cntt=kindd; if(ss[0])cntt+=ss[0]->cntt; if(ss[1])cntt+=ss[1]->cntt; if(kindd==0){ lenmx=r-l+1;locmx=l; }else{ lenmx=locmx=0; } if(ss[0]){ if(ss[0]->lenmx>lenmx){ lenmx=ss[0]->lenmx;locmx=ss[0]->locmx; } } if(ss[1]){ if(ss[1]->lenmx>=lenmx){ lenmx=ss[1]->lenmx;locmx=ss[1]->locmx; } } } }t[N*5]; int tot=0; data *root,*bz,*flag; data* newnode(int l,int r){ t[++tot]=data(l,r);return t+tot; } data* newnode(int x){ t[++tot]=data(x);return t+tot; } data* findpos(data* tr,int loc) { if(tr->l<=loc&&loc<=tr->r)return tr; if(loc>tr->r)return findpos(tr->ss[1],loc); if(loc<tr->l)return findpos(tr->ss[0],loc); } inline int pd(data* tr) { return tr==tr->pointt->ss[1]; } void xz(data* tr,int t,data* &root) { data* p=tr->pointt,*c=tr->ss[t]; if(!p)root=c; else p->ss[pd(tr)]=c; c->pointt=p; tr->ss[t]=c->ss[t^1]; if(c->ss[t^1]) c->ss[t^1]->pointt=tr; c->ss[t^1]=tr;tr->pointt=c; tr->up();c->up(); } void splay(data* tr,data* &root){ data *p,*g; while((p=tr->pointt)&&(g=p->pointt)){ int t1=pd(tr),t2=pd(p); if(t1==t2){xz(g,t2,root);xz(p,t1,root);} else {xz(p,t1,root);xz(g,t2,root);} } if(p!=0){ xz(p,pd(tr),root); } } void split(int l,int r){ splay(findpos(root,l),root); bz=root->ss[0]; if(bz){ root->ss[0]=0;bz->pointt=0;root->up(); } splay(findpos(root,r),root); flag=root->ss[1]; if(flag){ root->ss[1]=0;flag->pointt=0;root->up(); } } data* lmx(data* tr){ if(tr->ss[0])return lmx(tr->ss[0]); else return tr; } data* rmx(data* tr){ if(tr->ss[1])return rmx(tr->ss[1]); else return tr; } void merge(){ if(bz){ splay(lmx(root),root); //splay(rmx(root),root); root->ss[0]=bz;bz->pointt=root;root->up(); } if(flag){ splay(rmx(root),root); //splay(lmx(root),root); root->ss[1]=flag;flag->pointt=root;root->up(); } } void query(int l,int r){ split(l,r); //printf("%d %d ",root,cntt); printf("%d ",root->cntt); merge(); } void changed(int loc){ split(loc,loc);root=newnode(loc,loc); if(bz){ splay(rmx(bz),bz); if(bz->kindd==1){ root->ss[0]=bz;bz->pointt=root;root->up();bz=0; }else{ bz->r=root->r;bz->pointt=0;root=bz;root->up();bz=0; } } if(flag){ splay(lmx(flag),flag); if(flag->kindd==1) { root->ss[1]=flag; flag->pointt=root; root->up(); flag=0; } else { //printf("!");printf("%d ",lmx(root)->l); flag->l=root->l;flag->ss[0]=root->ss[0]; if(root->ss[0])root->ss[0]->pointt=flag; flag->pointt=0; root=flag;root->up();flag=0; } } } int insert(){ int loc=root->locmx+root->lenmx/2; split(loc,loc); if(loc>root->l) { root->ss[0]=newnode(root->l,loc-1); root->ss[0]->pointt=root; } if(locr) { root->ss[1]=newnode(loc+1,root->r);root->ss[1]->pointt=root; } root->kindd=1;root->cntt=1;root->l=root->r=loc;root->lenmx=root->locmx=0; root->up(); merge(); return loc; } int main(){ freopen("switch.in","r",stdin); freopen("switch.out","w",stdout); scanf("%d%d",&n,&q); int ff[N]; root=newnode(1,n); for(int i=1;i<=q;++i) { scanf("%d",&pos[i]); if(pos[i]==0) scanf("%d%d",&left[i],&right[i]); else a[++cnt]=i; //fo(j,1,q)ff[i]+=i; } sort(a+1,a+cnt+1,cmp); int last=-1,tot=0;// for(int i=1;i<=cnt;++i) { if(last!=pos[a[i]]) { last=pos[a[i]]; ++tot; } pos[a[i]]=tot; } for(int i=1;i<=q;++i) { if(pos[i]==0) query(left[i],right[i]); else { if(loc[pos[i]]==0) { loc[pos[i]]=insert(); }else { changed(loc[pos[i]]); loc[pos[i]]=0; } } } return 0; }