首页 > 代码库 > 【分块】【LCT】bzoj2002 [Hnoi2010]Bounce 弹飞绵羊
【分块】【LCT】bzoj2002 [Hnoi2010]Bounce 弹飞绵羊
分块,每个点统计还有几步弹出该块,以及它弹出块后的下一个节点是哪个点。
注意:update某个点的时候,会可能对当前块内 该点及以前的点 产生影响,所以对这部分点进行更新。
1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 int n,m,op,x,y,sz,a[200001],l[450],sum,num[200001],b[200001],c[200001]; 5 bool vis[200001]; 6 void makeblock() 7 { 8 int r;sz=sqrt(n); 9 for(sum=1;sum*sz<n;sum++)10 {11 l[sum]=(sum-1)*sz;12 r=sum*sz-1;13 for(int i=l[sum];i<=r;i++)14 num[i]=sum;15 }16 l[sum]=sz*(sum-1);17 r=n-1;18 for(int i=l[sum];i<=r;i++)19 num[i]=sum;20 }21 void init()22 {23 for(int i=0;i<n;i++)24 {25 int u=i,cnt=0;26 while(num[u]==num[i]){u+=a[u];cnt++;}27 b[i]=cnt;c[i]=u;28 }29 }30 inline int query(int u)31 {32 int res=0;33 while(u<n){res+=b[u];u=c[u];}34 return res;35 }36 inline void update(const int &p,const int &val)37 {38 a[p]=val;39 if(num[p+a[p]]!=num[p]){b[p]=1;c[p]=p+a[p];}40 else{b[p]=b[p+a[p]]+1;c[p]=c[p+a[p]];}41 for(int i=p;i>=l[num[p]];i--)42 if(i+a[i]<=p){b[i]=b[i+a[i]]+1;c[i]=c[i+a[i]];}43 }44 int Res,Num;char C,CH[20];45 inline int G()46 {47 Res=0;C=‘*‘; 48 while(C<‘0‘||C>‘9‘)C=getchar();49 while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();}50 return Res;51 }52 inline void P(int x)53 {54 Num=0; 55 while(x>0)CH[++Num]=x%10,x/=10;56 while(Num)putchar(CH[Num--]+48);57 putchar(‘\n‘);58 }59 int main()60 {61 n=G();for(int i=0;i<n;i++)a[i]=G();62 makeblock();init();m=G();63 for(int i=1;i<=m;i++)64 {65 op=G();66 if(op==1){x=G();P(query(x));}67 else{x=G();y=G();update(x,y);}68 }69 return 0;70 }
【分块】【LCT】bzoj2002 [Hnoi2010]Bounce 弹飞绵羊
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。