P3203 [HNOI2010]弹飞绵羊(LCT)

野性酷女 2023-08-17 17:21 129阅读 0赞

# 弹飞绵羊 #

[题目传送门][Link 1]

## 解题思路 ##

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; }

转载于:https://www.cnblogs.com/whisperlzw/p/11404163.html

[Link 1]: https://www.luogu.org/problem/P3203