首页 > 代码库 > [luoguP3203][HNOI2010]BOUNCE 弹飞绵羊（LCT）
[luoguP3203][HNOI2010]BOUNCE 弹飞绵羊（LCT）
传送门
每个点都会跳到另一个点，连边就是一棵树。
更改弹力就是换边。
求一个点跳多少次跳到终点就是求这个点的深度，那么只需要维护 size 域，access(n + 1) 然后 splay(x)，求 size[son[x][0]] 即可，
因为 splay 是以深度为关键字的，所以左端点就是深度比它小的。
——代码
1 #include <cstdio> 2 #include <iostream> 3 #define N 200010 4 #define min(x, y) ((x) < (y) ? (x) : (y)) 5 #define max(x, y) ((x) > (y) ? (x) : (y)) 6 #define swap(x, y) ((x) ^= (y) ^= (x) ^= (y)) 7 #define get(x) (son[f[x]][1] == (x)) 8 #define isroot(x) (son[f[x]][0] ^ (x) && son[f[x]][1] ^ (x)) 9 10 int n, k; 11 int a[N], f[N], size[N], rev[N], son[N][2], s[N]; 12 13 inline int read() 14 { 15 int x = 0, f = 1; 16 char ch = getchar(); 17 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; 18 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; 19 return x * f; 20 } 21 22 inline void update(int x) 23 { 24 if(x) 25 { 26 size[x] = 1; 27 if(son[x][0]) size[x] += size[son[x][0]]; 28 if(son[x][1]) size[x] += size[son[x][1]]; 29 } 30 } 31 32 inline void pushdown(int x) 33 { 34 if(x && rev[x]) 35 { 36 swap(son[x][0], son[x][1]); 37 if(son[x][0]) rev[son[x][0]] ^= 1; 38 if(son[x][1]) rev[son[x][1]] ^= 1; 39 rev[x] = 0; 40 } 41 } 42 43 inline void rotate(int x) 44 { 45 int old = f[x], oldf = f[old], wh = get(x); 46 47 if(!isroot(old)) 48 son[oldf][old == son[oldf][1]] = x; 49 f[x] = oldf; 50 51 son[old][wh] = son[x][wh ^ 1]; 52 f[son[old][wh]] = old; 53 54 son[x][wh ^ 1] = old; 55 f[old] = x; 56 57 update(old); 58 update(x); 59 } 60 61 inline void splay(int x) 62 { 63 int i, fa, t = 0; 64 s[++t] = x; 65 for(i = x; !isroot(i); i = f[i]) s[++t] = f[i]; 66 for(i = t; i >= 1; i--) pushdown(s[i]); 67 for(; !isroot(x); rotate(x)) 68 if(!isroot(fa = f[x])) 69 rotate(get(x) ^ get(fa) ? x : fa); 70 } 71 72 inline void access(int x) 73 { 74 for(int t = 0; x; t = x, x = f[x]) splay(x), son[x][1] = t, update(x); 75 } 76 77 inline void reverse(int x) 78 { 79 access(x); 80 splay(x); 81 rev[x] ^= 1; 82 } 83 84 inline void cut(int x, int y) 85 { 86 reverse(x); 87 access(y); 88 splay(y); 89 son[y][0] = f[x] = 0; 90 update(y); 91 } 92 93 inline void link(int x, int y) 94 { 95 reverse(x); 96 f[x] = y; 97 access(x); 98 } 99 100 inline int query(int x)101 {102 reverse(n + 1);103 access(x);104 splay(x);105 return size[son[x][0]];106 }107 108 int main()109 {110 int i, x, y, z;111 n = read();112 for(i = 1; i <= n; i++)113 {114 x = read();115 a[i] = f[i] = min(i + x, n + 1);116 size[i] = 1;117 }118 size[n + 1] = 1;119 k = read();120 for(i = 1; i <= k; i++)121 {122 z = read();123 x = read() + 1;124 if(z == 1) printf("%d\n", query(x));125 else126 {127 y = read();128 cut(x, a[x]);129 link(x, a[x] = min(x + y, n + 1));130 }131 }132 return 0;133 }
[luoguP3203][HNOI2010]BOUNCE 弹飞绵羊（LCT）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。