[HNOI2010]弹飞绵羊【LCT】

>Link

luogu P3203

---

>Description

一共有 $n$ 个排成一行的弹飞装置，序号为 $0$ 到 $n-1$，每个装置都有一个弹飞系数 $a$ ，表示在这个弹飞装置上可以弹到往后 $a$ 个装置的位置上。现在有 $m$ 个询问，每次询问：

1. 从第 $j$ 个弹飞装置出发要弹几次才能弹出去
2. 把第 $j$ 个弹飞装置的弹飞系数修改成 $k$

$1\le n\le 2\times 10^5，1\le m\le 10^5$

---

>解题思路

一个初步的想法，把每个装置都向它弹到的地方连一条边，弹到外面的就不连边，表示已经弹出去。每次查询就是询问某个装置走到底的路径长。可以很容易发现这实际上就是多棵树。

有改边操作，我们可以使用LCT来完成。
因为这是一（多）棵树，查询就可以：$access(x)\to splay(x)\to size[x]$，因为是走到根。
改边直接进行父亲、儿子关系的修改就可以了，还是因为这是一棵树

---

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010
using namespace std;

struct node
{
	int f, son[3], siz;
} t[N];
int n, m, a[N];

int identify (int x)
{
	if (t[t[x].f].son[0] == x) return 0;
	if (t[t[x].f].son[1] == x) return 1;
	return -1;
}
void update (int x)
{
	int ls = t[x].son[0];
	int rs = t[x].son[1];
	t[x].siz = 1;
	if (ls) t[x].siz += t[ls].siz;
	if (rs) t[x].siz += t[rs].siz;
}
void rorate (int x)
{
	int y = t[x].f, z = t[y].f;
	int k = identify (x), kk = identify (y);
	t[y].son[k] = t[x].son[k ^ 1], t[t[x].son[k ^ 1]].f = y;
	t[x].son[k ^ 1] = y, t[y].f = x;
	if (kk != -1) t[z].son[kk] = x;
	t[x].f = z;
	update (y);
	update (x);
}
void splay (int x)
{
	int y, k, kk;
	while (identify (x) != -1)
	{
		y = t[x].f;
		k = identify (x), kk = identify (y);
		if (kk != -1)
		{
			if (k == kk) rorate (y);
			else rorate (x);
		}
		rorate (x);
	}
}
void access (int x)
{
	int u = 0;
	while (x)
	{
		splay (x);
		t[x].son[1] = u;
		update (x);
		u = x;
		x = t[x].f;
	}
}
int askans (int x)
{
	access (x);
	splay (x);
	return t[x].siz;
}
void change (int x, int y)
{
	access (x);
	splay (x);
	t[t[x].son[0]].f = 0;
	t[x].son[0] = 0;
	update (t[x].f);
	if (y <= n) t[x].f = y;
	else t[x].f = 0;
}

int main()
{
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf ("%d", &a[i]);
		a[i] += i;
		if (a[i] > n) a[i] = 0;
		t[i] = (node){a[i], {0, 0, 0}, 1};
	}
	int x, y, z;
	scanf ("%d", &m);
	for (int i = 1; i <= m; i++)
	{
		scanf ("%d%d", &x, &y);
		if (x == 1) printf ("%d\n", askans (y + 1));
		else
		{
			scanf ("%d", &z);
			change (y + 1, y + 1 + z);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106