bzoj 2002: [Hnoi2010]Bounce 弹飞绵羊 （分块。）

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

HINT

第一次写分块。代码还是好理解的。 

分成每个块， 每块是有联系的，但是修改块内是互不影响的。

#include
using namespace std;
const int N = 2e5+100;
typedef long long ll;
inline ll read()
{ll x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int n,m,block,cnt;
int l[1000],r[1000],belong[N],st[N],pt[N],k[N];
int cal(int x){int sum = 0;while(2){sum += st[x];if (!pt[x]) break;x = pt[x];}return sum;
}
int main(){int x,y,op;n  = read();block = 1000;for (int i = 1; i <= n; ++i)k[i] = read();if (n % block) cnt = n / block + 1;else cnt = n / block;for (int i = 1; i <= n; ++i)belong[i] = (i-1)/block+1;for (int i = 1; i <= cnt; ++i)l[i] = (i-1)*block + 1, r[i] = i * block;r[cnt] = n;for (int i = n; i > 0; --i){if (i + k[i] > n) st[i] = 1;if (belong[i] == belong[i+k[i]])st[i] = st[i+k[i]]+1,pt[i] = pt[i+k[i]];else st[i] = 1,pt[i] = i + k[i];}scanf("%d",&m);for (int i = 0; i < m; ++i){op = read(); x = read(); x++;if (op == 1){int ans = cal(x);printf("%d\n",ans);} else{y = read();k[x] = y;for (int j = x; j >= l[belong[x]]; --j){if (belong[j] == belong[j+k[j]]) st[j] = st[j+k[j]] + 1,pt[j] = pt[j+k[j]]; else st[j] = 1,pt[j] = j+k[j];}}}return 0;
}

还可以用LCT 做。

每一个点向它弹到的位置连边。如果被弹飞了，那么这条边就不存在。

查询弹飞的步数，就是查询该点到其所属原树中根节点的路径的sizesize。

注意此题的一些特性。我们并不需要查询或者更改指定路径(x-y)(x−y)的信息。

也就是说，我们根本不需要换根！

原来需要换根的split,link,cutsplit,link,cut操作，我们可以根据题目特性适当调整一下。

• 查询原本需要splitsplit，我们直接access(x),splay(x)access(x),splay(x)，输出x的size。

• 连边原本需要linklink，题目保证了是一棵树，我们直接改xx的父亲，连轻边。

• 断边原本需要cutcut，然而我们确定其父亲的位置，access(x),splay(x)access(x),splay(x)后，x的父亲一定在x的左子树中（LCT总结中的性质1），直接双向断开连接。

#include
using namespace std;
const int N = 3e5;
int n,m,zhan[N],top,a[N];
struct Splay{int sum,rev,ch[2],fa;
}t[N];
void pushup(int x){t[x].sum = t[t[x].ch[0]].sum + t[t[x].ch[1]].sum + 1;
}
void reverse(int x){swap(t[x].ch[0],t[x].ch[1]);t[x].rev^=1;
}
void pushdown(int x){if (!t[x].rev) return;if (t[x].ch[0]) reverse(t[x].ch[0]);if (t[x].ch[1]) reverse(t[x].ch[1]);t[x].rev = 0;
}
bool isroot(int x){return t[t[x].fa].ch[0]!=x && t[t[x].fa].ch[1] != x;
}
void rotate(int x){int y = t[x].fa,z = t[y].fa;int k = t[y].ch[1] == x;if (!isroot(y)) t[z].ch[t[z].ch[1]== y] = x;t[x].fa = z;t[y].ch[k] = t[x].ch[k^1]; t[t[x].ch[k^1]].fa = y;t[x].ch[k^1] = y; t[y].fa = x;pushup(y); 
}
void splay(int x){zhan[++top] = x;for (int pos = x; !isroot(pos); pos = t[pos].fa)zhan[++top] = t[pos].fa;while(top) pushdown(zhan[top--]);while(!isroot(x)){int y = t[x].fa,  z = t[y].fa;if (!isroot(y)) (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);rotate(x);}pushup(x);
}void access(int x){for (int y = 0; x;y = x,x = t[x].fa){splay(x); t[x].ch[1] = y;pushup(x);}
}int main(){int x,y,z;scanf("%d",&n);for (int i = 1; i <= n; ++i){scanf("%d",&a[i]);if (i + a[i] <= n) t[i].fa = i+a[i];}scanf("%d",&m);for (int i = 0; i < m; ++i){scanf("%d",&z);if (z==1){scanf("%d",&x);++x;access(x); splay(x);printf("%d\n",t[x].sum);} else {scanf("%d%d",&x,&y); x++;access(x); splay(x);t[x].ch[0] = t[t[x].ch[0]].fa = 0;if (x + y <= n) t[x].fa = x+y;pushup(x);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！