首页 > 代码库 > bzoj4697: 猪
bzoj4697: 猪
Description
红学姐和黄学长是好朋友。红学姐有一只宠物，叫魔法猪。黄学长也有一只宠物，叫小奇。有 n 个猪圈排成一排
，魔法猪藏在某个猪圈中。为了找到魔法猪，小奇会向你询问一些猪圈中猪的个数和。在询问的过程中，魔法猪可
能会释放魔法来改变这些猪圈。
共有 m 次操作。每次操作是以下三种之一。
Q x y 询问从左到右第 x 个猪圈到第 y 个猪圈中猪的个数和。
C x y 将从左到右第 x 个猪圈中猪的个数变为 y。
M x y 将从左到右第 x 个猪圈移动到第 y 个猪圈的位置，并将第 y 个猪圈到第 x-1 个猪圈全部右移一格。保证
x>y。保证任何时候每个猪圈中猪的数量在 0 至 1000000 之间。
Input
第一行包含两个整数 n，m,其值均小于等于10^5
第二行 n 个整数表示从左到右每个猪圈中猪的个数。
接下来 m 行每行一个操作。
Output
对于每个询问操作，输出一行一个整数表示答案。
由于卡空间，这里考虑平衡树套分块以减小空间常数，若取块大小为B=O(logn)则不会增加时间复杂度
限制块大小为[B,2B-1]，但最后一块为[1,2B-1]，在插入删除时可能破坏这一性质，需要相应维护
插入：
若插入后块大小为2B，则将这个块分裂。
删除：
对最后一个块，若删除后块大小为0，则删去这一块。
对其余的块，若删除后块大小为B-1，则考虑下一个块：
若下一个块大小为B，则合并这两个块，
否则将下一个块的第一个元素移到当前块的末尾。
#include<cstdio>#include<cstdlib>const int B=10,B2=B*2,M=32768,N=100111;typedef long long i64;i64 _a;#define lc c[0]#define rc c[1]struct node{ int v[B2]; node*c[2]; i64 s2; int sz,len,rnd,s1; void init(int D){ lc=rc=0; sz=len=D; rnd=rand(); s2=s1; } void read(int D){ init(D); s1=0; for(int i=0;i<len;++i)scanf("%d",v+i),s1+=v[i]; s2=s1; } void get(node*a){ init(B); s1=0; for(int i=0,*b=a->v+B;i<B;++i)s1+=v[i]=b[i]; a->s1-=s1,a->len=B; s2=s1; } void up(){ sz=len,s2=s1; if(lc)sz+=lc->sz,s2+=lc->s2; if(rc)sz+=rc->sz,s2+=rc->s2; } void sum(int L,int R){ if(!this)return; if(L<=1&&R>=sz){ _a+=s2; return; } int ls=lc?lc->sz:0; if(L<=ls)lc->sum(L,R),L=ls+1; L-=ls,R-=ls; if(R>len)rc->sum(L-len,R-len),R=len; if(L==1&&R==len)_a+=s1; else for(--L;L<R;++L)_a+=v[L]; } void set(int w,int x){ int ls=lc?lc->sz:0; if(w<=ls)lc->set(w,x); else if(w>ls+len)rc->set(w-ls-len,x); else{ w-=ls+1; s1+=x-v[w]; v[w]=x; } up(); } node*chk(int d){ if(c[d]&&c[d]->rnd>rnd){ node*u=c[d]; c[d]=u->c[d^1]; u->c[d^1]=this; return up(),u->up(),u; } return up(),this; } node*del(int x); node*ins(int x);}ns[N/B+5],*ss[N/B+5],*rt,*tmp;int n,m,sp=0,flag,_pos;node*mg(node*a,node*b){ if(!a)return b; if(!b)return a; if(a->rnd>b->rnd){ a->rc=mg(a->rc,b); a->up(); return a; }else{ b->lc=mg(a,b->lc); b->up(); return b; }}node*node::del(int w){ int ls=lc?lc->sz:0; if(w<=ls)return lc=lc->del(w),chk(0); if(w>ls+len)return rc=rc->del(w-ls-len),chk(1); if(flag&&len<=B){ flag=0; for(int i=len-1;i>=0;--i)v[i+B-1]=v[i]; for(int i=0;i<B-1;++i)v[i]=tmp->v[i]; len+=B-1,sz+=B-1; s1+=tmp->s1,s2+=tmp->s1; ss[sp++]=tmp; return this; } _a=v[w-ls-1]; s1-=_a,s2-=_a; for(int i=w-ls;i<len;++i)v[i-1]=v[i]; --len,--sz; if(flag){ tmp->s1+=tmp->v[B-1]=_a; tmp->init(B); return lc=mg(lc,tmp),chk(0); } if(len<B){ if(!len)ss[sp++]=this; else flag=1,_pos=ls-w,tmp=this; return mg(lc,rc); } return this;}node*node::ins(int w){ int ls=lc?lc->sz:0; if(w<=ls)return lc=lc->ins(w),chk(0); if(w>ls+len+1)return rc=rc->ins(w-ls-len),chk(1); w-=ls+1; for(int i=len++;i>w;--i)v[i]=v[i-1]; v[w]=_a; s1+=_a,s2+=_a; if(len<B2)return up(),this; tmp=ss[--sp]; tmp->get(this); return rc=mg(tmp,rc),chk(1);}int main(){ scanf("%d%d",&n,&m); srand(n^m<<1^1512); for(int i=0,mx=n/B+1;i<mx;++i)ss[sp++]=ns+i; for(int D=B*3/2,l=1,r=D;l<=n;l+=D,r+=D){ if(r>n)r=n; node*w=ss[--sp]; w->read(r-l+1); rt=mg(rt,w); } for(;m;--m){ char o; int a,b; scanf(" %c %d%d",&o,&a,&b); if(o==‘Q‘-48){ _a=0; rt->sum(a,b); printf("%lld\n",_a); }else if(o==‘C‘-48){ rt->set(a,b); }else{ flag=0; rt=rt->del(a); if(flag){ _pos+=a+1; if(_pos<=n-1-tmp->len){ i64 a0=_a; rt=rt->del(_pos); _a=a0; }else{ tmp->init(tmp->len); rt=mg(rt,tmp); } } rt=rt->ins(b); } } return 0;}
bzoj4697: 猪
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。