东坑镇网站建设,什么网站可以做钟点工,cn网站,沈阳网站搭建正题
luogu 3203 金牌导航 LCT-2 题目大意
给你n个格子#xff0c;当你在第i个格子时#xff0c;可以往后跳aia_iai格#xff0c;让你进行几下操作#xff1a; 1.修改第i个数 2.查询在第i个格子跳多少下会跳出界 解题思路
往后跳相当于连接格子#xff0c;由此建立一…正题
luogu 3203 金牌导航 LCT-2 题目大意
给你n个格子当你在第i个格子时可以往后跳aia_iai格让你进行几下操作 1.修改第i个数 2.查询在第i个格子跳多少下会跳出界 解题思路
往后跳相当于连接格子由此建立一棵树
用LCT实现删边加边
建立一个额外的点为出界的点查询时判断距离即可 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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;
}
