[BZOJ2002][[Hnoi2010]Bounce 弹飞绵羊]

题目大意：

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

思路：

貌似还是一道LCT裸题啊。。。对于每个i，建边 (i,i+ki) ，形成的肯定是一棵树，修改弹力系数，就相当于在LCT上先 cut 原边然后再 link 新边，而询问弹几次会弹飞则是询问右子树的大小。所以在splay中维护一下子树大小就好了。

注意 i 的编号是[0,n−1]，为了方便可以 +1 ，而弹力装置可能会飞到外面去（ >=n+1 ），所以可以在 n+1 的位置设置一个虚拟节点方便操作。

代码：

#include <bits/stdc++.h> using namespace std; const int Maxn = 200005; const int Min(const int &a, const int &b) { return a < b ? a : b; } namespace IO { inline char get(void) { static char buf[1000000], *p1 = buf, *p2 = buf; if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin); if (p1 == p2) return EOF; } return *p1++; } inline void read(int &x) { x = 0; static char c; bool f = 0; for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') f = 1; for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); if (f) x = -x; } inline void write(int x) { if (!x) return (void)puts("0"); if (x < 0) putchar('-'), x = -x; static short s[12], t; while (x) s[++t] = x % 10, x /= 10; while (t) putchar('0' + s[t--]); putchar('\n'); } }; int fa[Maxn], c[Maxn][2], st[Maxn], top, size[Maxn], nxt[Maxn]; bool rev[Maxn]; inline bool isRt(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; } inline void pushDown(int x) { static int l, r; l = c[x][0], r = c[x][1]; if (rev[x]) { rev[l] ^= 1; rev[r] ^= 1; swap(c[x][0], c[x][1]); rev[x] ^= 1; } } inline void pushUp(int x) { size[x] = size[c[x][0]] + size[c[x][1]] + 1; } inline void rotate(int x) { int y = fa[x], z = fa[y], l, r; r = c[y][0] == x; l = r ^ 1; if (!isRt(y)) { if (c[z][0] == y) c[z][0] = x; else c[z][1] = x; } fa[x] = z; fa[y] = x; fa[c[x][r]] = y; c[y][l] = c[x][r]; c[x][r] = y; pushUp(y); pushUp(x); } inline void splay(int x) { st[top = 1] = x; for (int i = x; !isRt(i); i = fa[i]) st[++top] = fa[i]; while (top) pushDown(st[top--]); int y, z; while (!isRt(x)) { y = fa[x], z = fa[y]; if (!isRt(y)) { if (c[y][0] == x ^ c[z][0] == y) rotate(x); else rotate(y); } rotate(x); } } inline void access(int x) { int t = 0; while (x) { splay(x); c[x][1] = t; t = x; x = fa[x]; } } inline void rever(int x) { access(x); splay(x); rev[x] ^= 1; } inline void link(int x, int y) { rever(x); fa[x] = y; splay(x); } inline void cut(int x, int y) { rever(x); access(y); splay(y); c[y][0] = fa[x] = 0; } int n, m; int main(void) { //freopen("in.txt", "r", stdin); IO::read(n); int x, y, op; for (int i = 1; i <= n; i++) { IO::read(x); x = Min(x + i, n + 1); fa[i] = nxt[i] = x; size[i] = 1; } size[n + 1] = 1; IO::read(m); while (m--) { if (IO::read(op), op & 1) { IO::read(x); x++; rever(n + 1); access(x); splay(x); IO::write(size[c[x][0]]); } else { IO::read(x); IO::read(y); x++; y = Min(n + 1, x + y); cut(x, nxt[x]); nxt[x] = y; link(x, nxt[x]); } } return 0; }

完。

By g1n0st