bzoj2002 [Hnoi2010]Bounce 弹飞绵羊 （Link Cut Tree）

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<=100000Output对于每个i=1的情况，你都要输出一个需要的步数，占一行。 Sample Input 4 1 2 1 1 3 1 1 2 1 1 1 1 Sample Output 2 3思路：LCT只用维护一个size值。。。 设从i可以跳到next[i]，就在i与next[i]之间连边，超出n的统一记作n+1。代码：using namespace std;const int MAXN = 200005;int n, m;int nex[MAXN], siz[MAXN], fa[MAXN], tr[MAXN][2];bool rev[MAXN];int q[MAXN], top = 0;void pushup(int x) { siz[x] = siz[tr[x][0]] + siz[tr[x][1]] + 1; }void pushdown(int x) {int l = tr[x][0], r = tr[x][1];if (rev[x]) {rev[x] ^= 1;rev[l] ^= 1;rev[r] ^= 1;swap(tr[x][0], tr[x][1]);}}bool isroot(int x) {return tr[fa[x]][0] != x && tr[fa[x]][1] != x;}void rotate(int x) {int y = fa[x], z = fa[y];int l, r;if (tr[y][0] == x) l = 0;else l = 1;r = l ^ 1;if (!isroot(y)) {if (tr[z][0] == y) tr[z][0] = x;else tr[z][1] = x;}fa[x] = z;fa[y] = x;fa[tr[x][r]] = y;tr[y][l] = tr[x][r];tr[x][r] = y;pushup(y);pushup(x);}void splay(int x) {top = 0;q[++top] = x;for (int i = x; !isroot(i); i = fa[i])q[++top] = fa[i];for (int i = top; i; i–) pushdown(q[i]);while (!isroot(x)) {int y = fa[x], z = fa[y];if (!isroot(y)) {if (tr[y][0] == x ^ tr[z][0] == y) rotate(x);else rotate(y);}rotate(x);}}void access(int x) {int t = 0;while (x) {splay(x);tr[x][1] = t;t = x;x = fa[x];}}void makeroot(int x) {access(x);splay(x);rev[x] ^= 1;}void ) {makeroot(x);fa[x] = y;splay(x);}void cut() {makeroot(x);access(y);splay(y);tr[y][0] = fa[tr[y][0]] = 0;}int main() {scanf(“%d”, &n);int op, x, y;for (int i = 1; i <= n; i++) {scanf(“%d”, &x);fa[i] = x + i;siz[i] = 1;if (fa[i] > n + 1) fa[i] = n + 1;nex[i] = fa[i];}siz[n + 1] = 1;scanf(“%d”, &m);for (int i = 1; i <= m; i++) {scanf(“%d”, &op);if (op == 1) {scanf(“%d”, &x);x++;makeroot(n + 1);access(x);splay(x);printf(“%d\n”, siz[tr[x][0]]);} else {scanf(“%d %d”, &x, &y);x++;int t = min(x + y, n + 1);cut(x, nex[x]);link(x, t);nex[x] = t;}}return 0;}

好像有头大象在吸水。然后再去了芦笛岩，