首页 > 代码库 > 【分块】【LCT】bzoj2002 [Hnoi2010]Bounce 弹飞绵羊

【分块】【LCT】bzoj2002 [Hnoi2010]Bounce 弹飞绵羊

2024-07-21 23:32:23   218人阅读

分块，每个点统计还有几步弹出该块，以及它弹出块后的下一个节点是哪个点。

注意：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 弹飞绵羊


联系
我们