【LCT】弹飞绵羊（luogu 3203/金牌导航 LCT-2）

正题

luogu 3203
金牌导航 LCT-2

---

题目大意

给你n个格子，当你在第i个格子时，可以往后跳$a_i$格，让你进行几下操作：
1.修改第i个数
2.查询在第i个格子跳多少下会跳出界

---

解题思路

往后跳相当于连接格子，由此建立一棵树

用LCT实现删边，加边

建立一个额外的点，为出界的点，查询时判断距离即可

---

代码

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 200021 using namespace std; int n, x, q, a[N]; struct LCT {#define ls son[x][0]#define rs son[x][1]int p[N], s[N], fa[N], son[N][2];bool NR(int x){return fa[x] && (son[fa[x]][0] == x || son[fa[x]][1] == x);}bool IRS(int x){return son[fa[x]][1] == x;}void push_up(int x){s[x] = s[ls] + s[rs] + 1;return;}void pushr(int x){swap(ls, rs);p[x] ^= 1;return;}void push_down(int x){if (p[x]){if (ls) pushr(ls);if (rs) pushr(rs);p[x] = 0;}return;}void rotate(int x){int y = fa[x], z = fa[y], k = IRS(x), g = son[x][!k];if (NR(y)) son[z][IRS(y)] = x;if (g) fa[g] = y;son[x][!k] = y;son[y][k] = g;fa[x] = z;fa[y] = x;push_up(y);return;}void push_hall(int x){if (NR(x)) push_hall(fa[x]);push_down(x);}void Splay(int x){push_hall(x);while(NR(x)){if (NR(fa[x])){if (IRS(x) == IRS(fa[x])) rotate(fa[x]);else rotate(x);}rotate(x);}push_up(x);return;}void access(int x){for (int y = 0; x; x = fa[y = x])Splay(x), rs = y, push_up(x);}void make_root(int x){access(x);Splay(x);pushr(x);return;}int find_root(int x){access(x);Splay(x);while(ls) push_down(x), x = ls;Splay(x);return x;}void Split(int x, int y){make_root(x);access(y);Splay(y);return;}void link(int x, int y){make_root(x);if (find_root(y) != x) fa[x] = y;return;}void cut(int x, int y){make_root(x);if (find_root(y) == x && fa[y] == x && !son[y][0]){fa[y] = rs = 0;push_up(x);}return;} }T; void link(int x, int y)//连边 {if (x + y <= n) T.link(x, x + y);else T.link(x, n + 1); } void cut(int x, int y) {if (x + y <= n) T.cut(x, x + y);else T.cut(x, n + 1); } int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i){scanf("%d", &a[i]);link(i, a[i]);}scanf("%d", &q);while(q--){scanf("%d", &x);if (x == 1){scanf("%d", &x);x++;T.Split(n + 1, x);printf("%d\n", T.s[x] - 1);//查询两点之间的点数}else{scanf("%d", &x);x++;cut(x, a[x]);scanf("%d", &a[x]);link(x, a[x]);}}return 0; }

总结

以上是生活随笔为你收集整理的【LCT】弹飞绵羊（luogu 3203/金牌导航 LCT-2）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。