某天，Lostmonkey發(fā)明了一種超級彈力裝置，為了在他的綿羊朋友面前顯擺，他邀請小綿羊一起玩?zhèn)€游戲。游戲一開始，Lostmonkey在地上沿著一條直線擺上n個裝置，每個裝置設定初始彈力系數(shù)ki，當綿羊達到第i個裝置時，它會往后彈ki步，達到第i+ki個裝置，若不存在第i+ki個裝置，則綿羊被彈飛。綿羊想知道當它從第i個裝置起步時，被彈幾次后會被彈飛。為了使得游戲更有趣，Lostmonkey可以修改某個彈力裝置的彈力系數(shù)，任何時候彈力系數(shù)均為正整數(shù)。
Input
第一行包含一個整數(shù)n，表示地上有n個裝置，裝置的編號從0到n-1,接下來一行有n個正整數(shù)，依次為那n個裝置的初始彈力系數(shù)。第三行有一個正整數(shù)m，接下來m行每行至少有兩個數(shù)i、j，若i=1，你要輸出從j出發(fā)被彈幾次后被彈飛，若i=2則還會再輸入一個正整數(shù)k，表示第j個彈力裝置的系數(shù)被修改成k。對于20%的數(shù)據(jù)n,m<=10000，對于100%的數(shù)據(jù)n<=200000,m<=100000
Output
對于每個i=1的情況，你都要輸出一個需要的步數(shù)，占一行。
Sample Input
4 1 2 1 1 3 1 1 2 1 1 1 1
Sample Output
2 3
Hint
C++版本一
分塊
直接跳的話復雜度是O(nm)，顯然是無法接受的。顯然我們無法優(yōu)化詢問這個m，那么如何從n入手優(yōu)化呢？
如果跳的次數(shù)能有效減少，那么對于時間的優(yōu)化是巨大的，所以我們考慮預處理一下從某個點跳到某個點需要幾步
最直接的思考，倒著遞推O(n)，預處理每個點跳到終點要幾步？對于修改較少的輸入時可以接受的，可是一旦修改的次數(shù)增多，復雜度還是O(nm)，
那么取折衷的方案是，我們考慮把n個數(shù)字分成若干段，每一段的大小是sqrt(n)，然后預處理每一個點跳到另外的位置（該位置屬于另一個區(qū)塊，也有可能是不相鄰的區(qū)塊，因為一步可能跳很遠，比一塊的大小還遠），以及從這個點到另一個塊的那個位置需要的步數(shù)。這要查詢的時候最多只要sqrt(n)的跳躍就能出結果。對于修改，我們只需要修改要修改的那個點屬于的塊中每個點跳到另外塊的位置以及需要的步數(shù)即可，因為每個塊只有sqrt(n)個點，所以總體復雜度為O(m*sqrt(n))。
?
#include <iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include <stdio.h>
using namespace std;
const int N=200000+100;
int n,m,sq,num;
int a[N],bl[N],c[N],b[N], l[N], r[N];int main()
{while(~scanf("%d",&n)){sq=sqrt(n);num = n / sq;if(n % sq) num++;//不能整除加1//塊的范圍for(int i = 1; i <= num; i++){l[i] = (i - 1) * sq + 1;r[i] = i * sq;}r[num] = n;for(int i=1;i<=n;i++){bl[i]=(i-1)/sq+1;scanf("%d",&a[i]);}for(int i=n;i>=1;i--){b[i]=i+a[i];c[i]=1;if (b[i]<=n&&bl[i]==bl[b[i]]){c[i]=c[b[i]]+1;b[i]=b[b[i]];}//printf("%d %d\n",b[i],c[i]);}scanf("%d",&m);int i,j,k;while(m--){scanf("%d",&i);if(i==1){scanf("%d",&j);j++;int ans=0;while (n>=j){ans+=c[j];j=b[j];}printf("%d\n",ans);}else{scanf("%d%d",&j,&k);int I=j+1;a[I]=k;for(int t=r[bl[I]];t>=l[bl[I]];t--){b[t]=t+a[t];c[t]=1;if(b[t]<=n&&bl[t]==bl[b[t]]){c[t]=c[b[t]]+1;b[t]=b[b[t]];}//printf("%d %d\n",b[i],c[i]);}}}}//cout << "Hello world!" << endl;return 0;
}
C++版本二
LCT
Link?Cut?TreeLink?Cut?Tree 的模板題，當然這個模板沒有那么裸，操作也沒有那么多啦……?
話說LCTLCT確是一個很惡心的板子，我曾以為平衡樹就是極致的惡心了，沒想到LCTLCT刷新了我對代碼的印象的上界（曾經(jīng)是二逼平衡樹），但是彈飛綿羊不是很長（130130左右），真正惡心的板子在這里?
Sone1Sone1?
還沒寫，估計有200+200+
回到彈飛綿羊，我們可以定義一個虛擬節(jié)點n+1n+1，表示被彈飛。而如果節(jié)點ii能夠彈到jj（彈飛就設為n+1n+1），就將ii設為jj的兒子。因為每個ii都只有一個父親，并且它的父親編號一定比ii大，最終都會匯向n+1n+1，所以可以發(fā)現(xiàn)，這其實是一棵有根樹。
那么顯然，修改操作就是修改父親，查詢操作就是查詢深度。而修改父親和查詢深度都是LCTLCT很拿手的，我們就這樣做出來了。
PS:PS:查詢深度時，先Access(x)Access(x)，讓n+1n+1到xx變成一棵SplaySplay，然后Splay(x)Splay(x)，讓xx變成根，這時size[x]?1size[x]?1就是xx的深度了，所以還要維護一個sizesize數(shù)組
然后就是代碼了，這次加了注釋，就可以看懂了~
?
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 200005
int n,m,K[N];
char S[10];
namespace LCT
{int cnt,ch[N][2],fa[N],dt[N],siz[N];bool rv[N],tp[N];//節(jié)點個數(shù) 兒子 父親 翻轉懶標記 數(shù)據(jù) 是否為根inline void Push_Down(int x)//懶標記下傳{if(rv[x]){rv[x]=0;swap(ch[x][0],ch[x][1]);if(ch[x][0])rv[ch[x][0]]^=1;if(ch[x][1])rv[ch[x][1]]^=1;}}inline void Push_Up(int x)//標記上傳{siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}inline void Rotate(int x)//萬能旋轉{int y=fa[x],z=fa[fa[x]];if(!y||tp[x])return;int wh=(x==ch[y][1]);Push_Down(x);ch[y][wh]=ch[x][!wh];if(ch[y][wh])fa[ch[y][wh]]=y;ch[x][!wh]=y;fa[y]=x;if(!tp[y])ch[z][y==ch[z][1]]=x;fa[x]=z;tp[x]=tp[y],tp[y]=0;rv[x]=rv[y],rv[y]=0;Push_Up(y);}inline void Splay(int x)//翻轉至根{Push_Down(x);Push_Up(x);for(;!tp[x];Rotate(x)){int y=fa[x];if(!tp[y]){int z=fa[y];if((x==ch[y][1])==(y==ch[z][1]))Rotate(y);else Rotate(x);}}Push_Down(x);Push_Up(x);}inline int Access(int x)//LCT的象征{int last=0;while(x){Splay(x);if(ch[x][1])tp[ch[x][1]]=1;ch[x][1]=last;if(last)tp[last]=0;Push_Up(x);last=x;x=fa[x];}return last;}inline void Beroot(int x)//換根{Access(x);Splay(x);rv[x]^=1;Push_Down(x);Push_Up(x);}inline void Link(int u,int v)//鏈接(u->v){Beroot(u);Access(v);fa[u]=v,tp[u]=1;}inline void Cut(int u,int v)//刪除(u->v){Beroot(u);Splay(v);if(fa[v]==u)fa[v]=0;elsefa[u]=ch[v][0]=0,tp[u]=1;Push_Up(v);Push_Up(u);Push_Up(v);Push_Up(u);}inline void Link_Cut(int u,int v,int w)//刪除(u->v)并鏈接(u->w){Cut(u,v);Link(u,w);}inline int Find_Root(int x)//找根{Access(x);Splay(x);while(ch[x][0]){Push_Down(x);x=ch[x][0];}return x;}inline bool Query_Linked(int u,int v)//判斷是否連通{return Find_Root(u)==Find_Root(v);}inline int Query_Deep(int x)//求深度{Access(x);Splay(x);return siz[x]-1;}inline void Init(int n)//初始化{cnt=n;memset(ch,0,sizeof(ch));memset(fa,0,sizeof(fa));memset(dt,0,sizeof(dt));memset(tp,1,sizeof(tp));memset(rv,0,sizeof(rv));for(int i=1;i<=n;i++)siz[i]=1;}
}
int Read()
{int p=0;char c=getchar();while(c>'9'||c<'0')c=getchar();while(c>='0'&&c<='9')p=p*10+c-'0',c=getchar();return p;
}
void Solve()
{for(int i=1;i<=m;i++){int opt;opt=Read();if(opt==1){int p=Read();printf("%d\n",LCT::Query_Deep(p+1));}else{int a=Read(),b=Read();a++;LCT::Link_Cut(a,min(a+K[a],n+1),min(a+b,n+1));LCT::Beroot(n+1);K[a]=b;}}
}
void Init()
{n=Read();LCT::Init(n+1);for(int i=1;i<=n;i++){K[i]=Read();LCT::Link(i,min(i+K[i],n+1));}LCT::Beroot(n+1);m=Read();
}
int main()
{Init();Solve();
}
?
總結
以上是生活随笔為你收集整理的Bounce 弹飞绵羊的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
