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

分析：
我們要把知道題轉化為樹形結構
每個彈射裝置都只能彈向一個固定的位置
這是一對一的關系，就好像樹上的爸爸和兒子
所以就把每個節點當作兒子，連到下一個位置（爸爸）

那要是彈飛了怎么辦呢
我們把所有彈飛的綿羊都連到一個不存在的位置（比如說n+1）
整體思路還是很好想的
然而只有一個點我想不明白
就是，初始的時候正常連邊，無論在查詢時還是改變值時，x++
望神犇能幫忙解釋一下

這里寫代碼片 #include<cstdio> #include<cstring> #include<iostream>using namespace std;const int N=100001; int pre[N],ch[N][2],q[N],size[N]; bool rev[N]; int n,a[N],m;int get(int bh) {return (ch[pre[bh]][0]==bh ? 0:1); }int isroot(int bh) {return ch[pre[bh]][0]!=bh&&ch[pre[bh]][1]!=bh; }void push(int bh) {if (rev[bh]){rev[bh]^=1;rev[ch[bh][0]]^=1;rev[ch[bh][1]]^=1;swap(ch[bh][0],ch[bh][1]);} }void update(int bh) {if (bh){size[bh]=1;if (ch[bh][0]) size[bh]+=size[ch[bh][0]];if (ch[bh][1]) size[bh]+=size[ch[bh][1]];} }void rotate(int bh) {int fa=pre[bh];int grand=pre[fa];int wh=get(bh);if (!isroot(fa)) ch[grand][ch[grand][0]==fa ? 0:1]=bh;ch[fa][wh]=ch[bh][wh^1];pre[ch[fa][wh]]=fa;ch[bh][wh^1]=fa;pre[fa]=bh;pre[bh]=grand;update(fa);update(bh); }void splay(int bh) {int top=0;q[++top]=bh;for (int i=bh;!isroot(i);i=pre[i])q[++top]=pre[i];while (top) push(q[top--]);for (int fa;!isroot(bh);rotate(bh))if (!isroot(fa=pre[bh]))rotate(get(bh)==get(fa) ? fa:bh); }void expose(int bh) {int t=0;while (bh){splay(bh);ch[bh][1]=t;t=bh;bh=pre[bh];} }void makeroot(int bh) {expose(bh);splay(bh);rev[bh]^=1; }void link(int x,int y) {makeroot(x);pre[x]=y;splay(x); }void cut(int x,int y) {makeroot(x);expose(y);splay(y);ch[y][0]=pre[x]=0; }int main() {scanf("%d",&n);for (int i=1;i<=n;i++){int u;scanf("%d",&u);if (i+u<=n) link(i,i+u),a[i]=i+u;else link(i,n+1),a[i]=n+1;size[i]=1; //初始值不要忘 }size[n+1]=1;scanf("%d",&m);for (int i=1;i<=m;i++){int opt,x,y;scanf("%d",&opt);if (opt==1){scanf("%d",&x);x++; //makeroot(n+1); ///???expose(x);splay(x);printf("%d\n",size[ch[x][0]]);}else {scanf("%d%d",&x,&y);x++; //cut(x,a[x]); if (x+y<=n) a[x]=x+y;else a[x]=n+1;link(x,a[x]); }}return 0; }

轉載于:https://www.cnblogs.com/wutongtong3117/p/7673558.html

總結

以上是生活随笔為你收集整理的bzoj2002Bounce 弹飞绵羊的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。