弹飞绵羊
解题思路
LCT。
将每个节点的权值设为\(1\)，连接\(i\)和\(i+ki\)，被弹飞就连上\(n\)，维护权值和\(sum[]\)。从\(j\)弹飞需要的次数就是\(split(j,n)\)后，\(sum[i]-1\)的值。修改弹力系数，即为断开\(i\)和旧的\(i+ki\)的连接，然后连上\(i\)和新的\(i+ki\)。
为了方便，以下代码把下标都加一了，即原编号变为\(1-n\)，弹飞设为\(n+1\)。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int fa[N], ch[N][2], siz[N], rev[N], sta[N], v[N];
inline bool get(int x)
{
return ch[fa[x]][1] == x;
}
inline bool isroot(int x)
{
return (!fa[x] || ch[fa[x]][1] != x && ch[fa[x]][0] != x);
}
inline void push_up(int x)
{
siz[x] = siz[ch[x][1]] + siz[ch[x][0]] + 1;
}
inline void rotate(int x)
{
int y = fa[x], z = fa[y];
bool u = get(x);
ch[y][u] = ch[x][u^1], fa[ch[x][u^1]] = y;
if(!isroot(y))
ch[z][get(y)] = x;
fa[x] = z;
ch[x][u^1] = y, fa[y] = x;
push_up(y), push_up(x);
}
inline void pushr(int x)
{
swap(ch[x][1], ch[x][0]);
rev[x] ^= 1;
}
inline void push_down(int x)
{
if(rev[x]){
pushr(ch[x][0]), pushr(ch[x][1]);
rev[x] = 0;
}
}
inline void splay(int x)
{
int pos = 0;
sta[++pos] = x;
for(int i = x; !isroot(i); i = fa[i])
sta[++pos] = fa[i];
while(pos)
push_down(sta[pos--]);
while(!isroot(x)){
int y = fa[x];
if(!isroot(y))
get(x) == get(y) ? rotate(y): rotate(x);
rotate(x);
}
}
inline void access(int x)
{
for(int y = 0; x; y = x, x = fa[x])
splay(x), ch[x][1] = y, push_up(x);
}
inline void make_root(int x)
{
access(x); splay(x);
pushr(x);
}
inline void split(int x, int y)
{
make_root(x);
access(y);splay(y);
}
inline void link(int x, int y)
{
make_root(x);
fa[x] = y;
}
inline void cut(int x, int y)
{
split(x, y);
fa[x] = ch[y][0] = 0;
push_up(y);
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i ++){
scanf("%d", &v[i]);
siz[i] = 1;
}
siz[n + 1] = 1;
for(int i = 1; i <= n; i ++){
if(i + v[i] <= n)
link(i, i + v[i]);
else
link(i, n + 1);
}
int m;
scanf("%d", &m);
for(int i = 1; i <= m; i ++){
int opt, x;
scanf("%d%d", &opt, &x);
++x;
if(opt == 1){
split(n + 1, x);
printf("%d\n", siz[x] - 1);
}
else {
int k;
scanf("%d", &k);
if(x + v[x] <= n)
cut(x, x + v[x]);
else
cut(x, n + 1);
if(x + k <= n)
link(x, x + k);
else
link(x, n + 1);
v[x] = k;
}
}
return 0;
}