题解 P3968 【[TJOI2014]电源插排】

楼上说，标算应该是线段树+```set```。我写的就是```std::set```+```std::map```+动态开点线段树。 s1维护各个空区间的左右端点，s2维护区间的长度和左端点，map记录学生对应的插排。插入时，从s2中找出最大区间长度，修改s1和s2；删除时，从s1中找出两侧的区间，修改s1和s2。查询时用动态开点线段树统计答案。 祝NOIp2018rp++！ ``` #include<cstdio> #include<cctype> #include<utility> #include<set> #include<map> #define PII std::pair<int,int> #define IT std::set<PII>::iterator int Read() { int x=0;char c=getchar(); while(!isdigit(c)) { c=getchar(); } while(isdigit(c)) { x=x*10+(c&15); c=getchar(); } return x; } std::set<PII> s1; std::set<PII> s2; std::map<int,int> stu; int Insert() { int l=s2.rbegin()->second; int r=s2.rbegin()->second+s2.rbegin()->first-1; int pos=(l+r+1)>>1;//坑点，记得这个加1 s2.erase(--s2.end()); s1.erase(PII(l,r)); if(l!=pos) { s1.insert(PII(l,pos-1)); s2.insert(PII(pos-1-l+1,l)); } if(r!=pos) { s1.insert(PII(pos+1,r)); s2.insert(PII(r-pos,pos+1)); } return pos; } void Erase(int pos) { IT back=s1.lower_bound(PII(pos,pos)); IT front=back; --front; int l=pos,r=pos; if(front->second==pos-1) { l=front->first; s2.erase(PII(front->second-front->first+1,front->first)); s1.erase(front); } if(back->first==pos+1) { r=back->second; s2.erase(PII(back->second-back->first+1,back->first)); s1.erase(back); } s1.insert(PII(l,r)); s2.insert(PII(r-l+1,l)); } struct seg { int l,r,sum; int ch[2]; } tree[3000005]; int size=1; void Add(int pos,int val,int L,int R,int idx) { if(L==R) tree[idx].sum+=val; else { int mid=(L+R)>>1; if(pos<=mid) { if(!tree[idx].ch[0]) tree[idx].ch[0]=++size; Add(pos,val,L,mid,tree[idx].ch[0]); } else { if(!tree[idx].ch[1]) tree[idx].ch[1]=++size; Add(pos,val,mid+1,R,tree[idx].ch[1]); } tree[idx].sum=tree[tree[idx].ch[0]].sum+tree[tree[idx].ch[1]].sum; } } int Query(int l,int r,int L,int R,int idx) { if(l<=L&&R<=r) return tree[idx].sum; else { int mid=(L+R)>>1; int ans=0; if(l<=mid) { if(!tree[idx].ch[0]) tree[idx].ch[0]=++size; ans+=Query(l,r,L,mid,tree[idx].ch[0]); } if(r>mid) { if(!tree[idx].ch[1]) tree[idx].ch[1]=++size; ans+=Query(l,r,mid+1,R,tree[idx].ch[1]); } return ans; } } int main() { int n=Read(),q=Read(); s1.insert(PII(1,n)); s2.insert(PII(n,1)); int k,l,r,pos; while(q--) { k=Read(); if(!k) { l=Read(),r=Read(); printf("%d\n",Query(l,r,1,n,1)); } else { if(stu[k]==0) { pos=stu[k]=Insert(); Add(pos,1,1,n,1); } else { Erase(pos=stu[k]); Add(pos,-1,1,n,1); stu[k]=0; } } } return 0; } ```