bzoj5155 [Tjoi2014]电源插排

bzoj5155 [Tjoi2014]电源插排

​​ Description

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

第一行是两个整数N和Q，表示插排数量和询问数量。 接下来Q行，每一行以一个整数K开头，如果K为0， 接下来就是两个整数L和R(1≤L≤R≤N)，表示一个询问。否则表示编号为K的学生到来或离开(K≤109)。 K的奇数次出现表示到来，偶数次出现表示离开。每个学生的编号都是唯一的。 N ≤ 10^9, Q ≤ 10^5

Output

对于每一个询问，输出一个整数，表示询问区间内有多少个插排已经被使用了。

Sample Input

7 10 1 2 3 0 1 2 0 4 7 0 2 5 20 0 6 6 99 0 4 6 Sample Output

1 2 2 1 3 HINT

Source

动态开点线段树 模板题 注意bzoj交的时候我的代码里unordered_map不可用 换成map即可

#include#include#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if(T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+100;unordered_map mm,id;int num,n,q,root; struct node{int left,right,v,ls,rs,mx;node(){v=0;}}tree[N*40];inline void update(int x,int L,int R){ static int l,r,lls,lrs,lmx,rls,rrs,rmx,lsum,rsum,mid; l=tree[x].left,r=tree[x].right;mid=L+R>>1; if (!l) lls=lrs=lmx=lsum=mid-L+1; else lls=tree[l].ls,lrs=tree[l].rs,lmx=tree[l].mx,lsum=tree[l].v; if (!r) rls=rrs=rmx=rsum=R-mid; else rls=tree[r].ls,rrs=tree[r].rs,rmx=tree[r].mx,rsum=tree[r].v; tree[x].mx=max(lmx,rmx); tree[x].mx=max(tree[x].mx,lrs+rls); tree[x].ls=(lls==mid-L+1)?lls+rls:lls; tree[x].rs=(rrs==R-mid)?rrs+lrs:rrs; tree[x].v=lsum+rsum;}inline void init(int &x,int l,int r){ x=++num;tree[x].mx=tree[x].ls=tree[x].rs=tree[x].v=r-l+1;}inline void insert1(int &x,int l,int r,int p,int v){ if (!x) init(x,l,r);int mid=l+r>>1; if (l==r) { tree[x].v+=v;if (!tree[x].v)tree[x].mx=tree[x].ls=tree[x].rs=tree[x].v=0; else tree[x].mx=tree[x].ls=tree[x].rs=tree[x].v=1;return; } if (p<=mid) insert1(tree[x].left,l,mid,p,v); else insert1(tree[x].right,mid+1,r,p,v);update(x,l,r);}inline int query(int &x,int l,int r,int len){ if(l==r) return l;if (!x) init(x,l,r);int mid=l+r>>1; if (!tree[x].left) init(tree[x].left,l,mid);if (!tree[x].right)init(tree[x].right,mid+1,r); if (tree[tree[x].right].mx>=len) return query(tree[x].right,mid+1,r,len); if (tree[tree[x].left].rs+tree[tree[x].right].ls>=len) return mid+tree[tree[x].right].ls; return query(tree[x].left,l,mid,len);}inline int qr(int &x,int l,int r,int l1,int r1){ if(!x) init(x,l,r);int mid=l+r>>1; if(l1<=l&&r1>=r) return tree[x].v; int tmp=0; if (l1<=mid) tmp+=qr(tree[x].left,l,mid,l1,r1); if (r1>mid) tmp+=qr(tree[x].right,mid+1,r,l1,r1);return tmp;}inline void print(int x,int l,int r){ int mid=l+r>>1; if (tree[x].left) print(tree[x].left,l,mid); printf("%d %d %d %d %d %d\n",l,r,tree[x].v,tree[x].mx,tree[x].ls,tree[x].rs); if (tree[x].right) print(tree[x].right,mid+1,r);}int main(){ freopen("bzoj5155.in","r",stdin); n=read();q=read();init(root,1,n); while(q--){ int k=read(); if (!k){ int l=read(),r=read(); printf("%d\n",r-l+1-qr(root,1,n,l,r));continue; }++mm[k];if(mm[k]&1){int len=tree[root].mx; int r=query(root,1,n,len); if (len&1) id[k]=r-(len>>1),insert1(root,1,n,id[k],-1); else id[k]=r-(len>>1)+1,insert1(root,1,n,id[k],-1); // print(root,1,n);puts("---"); }else insert1(root,1,n,id[k],1); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。