题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=4764
题解
如果 \(a_i > 0\) 的话，那么就是 bzoj2002 的原题。直接用 LCT 维护就可以了。
但是现在这个题因为 \(a_i\) 任意，所以不能保证每个点向弹向的点连边一定是一棵树。
但是因为每个点的出边只有一条，所以一定是基环树森林。
考虑如何用 LCT 维护基环树。
首先这个环一定出现在根的位置。所以不妨用一个变量存一下这个根有没有额外的环边。
link 的时候，如果不连通，那么就直接连接。如果联通，那么就记录一下额外边。
cut 的时候，如果 cut 的是额外边那么直接把记录删掉。如果不是，直接 cut。但是这样可能会把根和它的额外边的点分离，这时候额外边就可以转正了。
其实还想到一个做法。
先求出每条边的消失的时间。然后每条边以这个东西为权值用 LCT 维护最大生成树。同时维护这个生成树中有没有环边。
加边的时候就是一般的生成树维护；
删边时候如果不是环边就直接 cut，不用考虑转正的问题了。
时间复杂度 \(O(m\log n)\)。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int N = 200000 + 7;
#define lc c[0]
#define rc c[1]
int n, m;
int a[N], ex[N];
struct Node { int c[2], fa, s; } t[N];
int st[N];
inline bool isroot(int o) { return t[t[o].fa].lc != o && t[t[o].fa].rc != o; }
inline bool idtfy(int o) { return t[t[o].fa].rc == o; }
inline void connect(int fa, int o, int d) { t[fa].c[d] = o, t[o].fa = fa; }
inline void pushup(int o) { t[o].s = t[t[o].lc].s + t[t[o].rc].s + 1; }
inline void rotate(int o) {
int fa = t[o].fa, pa = t[fa].fa, d1 = idtfy(o), d2 = idtfy(fa), b = t[o].c[d1 ^ 1];
if (!isroot(fa)) t[pa].c[d2] = o; t[o].fa = pa;
connect(o, fa, d1 ^ 1), connect(fa, b, d1);
pushup(fa), pushup(o);
assert(!t[0].lc && !t[0].rc);
}
inline void splay(int o) {
while (!isroot(o)) {
int fa = t[o].fa;
if (isroot(fa)) rotate(o);
else if (idtfy(o) == idtfy(fa)) rotate(fa), rotate(o);
else rotate(o), rotate(o);
}
}
inline void access(int o) {
for (int x = 0; o; o = t[x = o].fa)
splay(o), t[o].rc = x, pushup(o);
}
inline int getrt(int o) {
access(o), splay(o);
while (t[o].lc) o = t[o].lc;
return splay(o), o;
}
inline void link(int x, int y) { // x -> y
splay(x);
assert(!t[x].fa);
t[x].fa = y;
}
inline void cut(int x, int y) { // x -> y
access(y), splay(x);
assert(t[x].fa == y);
t[x].fa = 0;
}
inline void work() {
while (m--) {
int opt, x;
read(opt), read(x);
if (opt == 1) {
int rt = getrt(x);
if (ex[rt]) puts("-1");
else access(x), splay(x), printf("%d\n", t[x].s);
} else {
if (x + a[x] <= n && x + a[x] > 0) {
if (x + a[x] == ex[x]) ex[x] = 0;
else {
cut(x, x + a[x]);
int rt = getrt(x + a[x]);
if (ex[rt] && getrt(ex[rt]) != rt) link(rt, ex[rt]), ex[rt] = 0;
}
}
read(a[x]);
if (x + a[x] <= n && x + a[x] > 0) {
if (getrt(x + a[x]) == x) ex[x] = x + a[x];
else link(x, x + a[x]);
}
}
}
}
inline void init() {
read(n), read(m);
for (int i = 1; i <= n; ++i) {
read(a[i]);
if (i + a[i] <= n && i + a[i] > 0) {
int y = i + a[i];
if (getrt(y) == i) ex[i] = y;
else link(i, y);
}
}
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}