BZOJ 2002
题意：见上。
如果没有修改就是个递推……
有修改的话我们将这个递推状态抽象成图论的点，然后发现这是一棵树
然后修改相当于断边连边，那么就是 LCT 裸题了。
这题也可以分块，每个块维护
- $f[i]$表示从$i$开始，跳出所在块的步数
- $to[i]$表示跳出所在块后到了哪里
知识点
1、递推/DP等状态抽象成图论的点，树、DAG图等
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
#define lc ch[x][0]
#define rc ch[x][1]
const int MAXN = 200000 + 5;
int ch[MAXN][2], fa[MAXN], sumv[MAXN], rev[MAXN];
// ch: ??????,fa: ????,val: ???,xorv: ?????, rev: ????
int n, q, top, stk[MAXN];
int ki[MAXN];
int isRt(int x) {return ch[fa[x]][0] != x && ch[fa[x]][1] != x;} //???Splay???
int rel(int x) {return ch[fa[x]][1] == x;} // ? Splay
void prorev(int x) {swap(lc, rc), rev[x] ^= 1;} // ?????? (????)
void pushup(int x) {sumv[x] = sumv[lc] + sumv[rc] + 1;} //????
void pushdown(int x) { //????
if (rev[x]) {
if (lc) prorev(lc);
if (rc) prorev(rc);
rev[x] = 0;
}
}
void rotate(int x) { // ? Splay
pushdown(fa[x]), pushdown(x);
int y = fa[x], z = fa[y], k = rel(x), w = ch[x][k ^ 1];
if (!isRt(y)) ch[z][rel(y)] = x;
fa[x] = z; // y ??? (z, y) ???,???? (??? Splay ???? 1)
ch[y][k] = w, fa[w] = y;
ch[x][k ^ 1] = y, fa[y] = x;
pushup(y), pushup(x);
}
void splay(int x) { // ? Splay
top = 0;
stk[++top] = x;
for (int pos = x; !isRt(pos); pos = fa[pos]) stk[++top] = fa[pos];
while (top) pushdown(stk[top--]); // ? x ?????????????? pushdown (??? Splay ???? 2)
//???1:???? isRt ???,????pushdown
while (!isRt(x)) { // (??? Splay ???? 3.1)
int y = fa[x];
if (!isRt(y)) { // (??? Splay ???? 3.2)
if (rel(x) == rel(y)) rotate(y); else rotate(x);
}
rotate(x);
}
//pushup(x); ??????
}
void access(int x) { // ????? x ???????????,??? x ????????????????
for (int y = 0; x; y = x, x = fa[x])
splay(x), rc = y, pushup(x);
}
void makeRt(int x) { // ??????
access(x), splay(x);
prorev(x);
}
int findRt(int x) { // ????? x ??
access(x), splay(x);
while (pushdown(x), lc) x = lc;
splay(x); // splay ????
return x;
}
void split(int x, int y) { // ???????? x-y
makeRt(x);
access(y), splay(y); // splay ????
//???2:?(x)?y??????,???? access ??,y ??????,?????
}
void link(int x, int y) { // ?????? x-y
makeRt(x);
if (findRt(y) != x) fa[x] = y;
}
void cut(int x, int y) { // ?????? x-y
makeRt(x);
if (findRt(y) == x && fa[y] == x && !ch[y][0]) {
fa[y] = rc = 0;
pushup(x);
}
}
void clean() {
ms(ch, 0), ms(fa, 0), ms(sumv, 0), ms(stk, 0), ms(rev, 0);
}
int solve() {
clean();
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &ki[i]);
if (i + ki[i] > n) link(i, n + 1); else link(i, i + ki[i]);
}
scanf("%d", &q);
while (q--) {
int ty; scanf("%d", &ty);
if (ty == 1) {
int i; scanf("%d", &i);
++i;
split(i, n + 1);
printf("%d\n", sumv[n + 1] - 1);
} else {
int i, k; scanf("%d%d", &i, &k);
++i;
if (i + ki[i] > n) cut(i, n + 1); else cut(i, i + ki[i]);
ki[i] = k;
if (i + ki[i] > n) link(i, n + 1); else link(i, i + ki[i]);
}
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
