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

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

2024-10-21 07:45:39   212人阅读

Description

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

Input

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

Output

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

Sample Input

4
1 2 1 1
3
1 1
2 1 1
1 1

Sample Output

2
3
直接模拟肯定超时
考虑分块优化
(其实是不会lct辣！)
 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<cmath> 5 using namespace std; 6  7 inline int read(){ 8     char ch; 9     int re=0;10     bool flag=0;11     while((ch=getchar())!=‘-‘&&(ch<‘0‘||ch>‘9‘));12     ch==‘-‘?flag=1:re=ch-‘0‘;13     while((ch=getchar())>=‘0‘&&ch<=‘9‘)  re=re*10+ch-‘0‘;14     return flag?-re:re;15 }16 17 const int maxn=200001;18 19 int n,m;20 //b[][1]跳到下一分块中的位置 21 //b[][0]跳到下一分块需要的步数 22 //c[]分块序号 23 int a[maxn],b[maxn][2],c[maxn];24 25 int main(){26     //freopen("temp.in","r",stdin);27     n=read();28     for(int i=0;i<n;i++)  a[i]=read();29     for(int i=0,v=1,h=(int)sqrt(n);i<n;i++){30         c[i]=v;31         if((i+1)%h==0)  v++;32     }33     for(int i=n-1;i>=0;i--){34         //跳出分块或弹飞 35         if(i+a[i]>n-1||c[i+a[i]]!=c[i])  b[i][1]=i+a[i];36         else  b[i][1]=b[i+a[i]][1];37         //记录多少步跳出分块 38         if(c[i+a[i]]!=c[i])  b[i][0]=1;39         else  b[i][0]=b[i+a[i]][0]+1;40     }41     m=read();42     int opt,pos,num,ans;43     while(m--){44         opt=read();45         if(opt==1){46             pos=read();47             ans=0;48             while(pos<=n-1){49                 ans+=b[pos][0];50                 pos=b[pos][1];51             }52             if(ans==0)  puts("1");53             else  printf("%d\n",ans);54         }55         else{56             pos=read();  num=read();57             a[pos]=num;58             if(pos+num>n-1||c[pos+num]!=c[pos])  b[pos][1]=pos+num;59             else  b[pos][1]=b[pos+num][1];60             if(c[pos+num]!=c[pos])  b[pos][0]=1;61             else  b[pos][0]=b[pos+num][0]+1;62             for(int i=pos-1;i>=0;i--){63                 if(c[i]!=c[pos])  break;64                 if(i+a[i]<=n-1&&c[i+a[i]]==c[i])  b[i][1]=b[i+a[i]][1];65                 if(c[i+a[i]]==c[i])  b[i][0]=b[i+a[i]][0]+1;66             }67         }68     }69     return 0;70 }

 

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


联系
我们