傳送門：http://www.lydsy.com/JudgeOnline/problem.php?id=2002

第一道LCT，調(diào)了3天，發(fā)現(xiàn)是智障bug，我的青春。。。

主要參考了黃學長的代碼，也沒啥好說的，反正就是LCT，就當存一份模版好了。

#include <cstdio>const int maxn = 200005;int n, m, t1, t2, t3, ori_tree_fa[maxn]; int left[maxn], right[maxn], fa[maxn], siz[maxn], root; int stk[maxn], top, pushdown_tem; bool rev[maxn];inline void pushup(int x) {siz[x] = siz[left[x]] + siz[right[x]] + 1; } inline void pushdown(int x) {if (rev[x]) {rev[x] = false;rev[left[x]] = !rev[left[x]];rev[right[x]] = !rev[right[x]];pushdown_tem = left[x];left[x] = right[x];right[x] = pushdown_tem;} } inline bool isroot(int x) {return left[fa[x]] != x && right[fa[x]] != x; } inline void leftrotate(int x) {int y = fa[x];if (!isroot(y)) {if (y == left[fa[y]]) {left[fa[y]] = x;}else {right[fa[y]] = x;}}fa[x] = fa[y];right[y] = left[x];fa[left[x]] = y;fa[y] = x;left[x] = y;pushup(y);pushup(x); } inline void rightrotate(int x) {int y = fa[x];if (!isroot(y)) {if (y == left[fa[y]]) {left[fa[y]] = x;}else {right[fa[y]] = x;}}fa[x] = fa[y];left[y] = right[x];fa[right[x]] = y;fa[y] = x;right[x] = y;pushup(y);pushup(x); } inline void splay(int x) {int p;top = 0;stk[top++] = x;for (int i = x; !isroot(i); i = fa[i]) {stk[top++] = fa[i];}for (int i = top - 1; i >= 0; --i) {pushdown(stk[i]);}while (!isroot(x)) {p = fa[x];if (isroot(p)) {if (x == right[p]) {leftrotate(x);}else {rightrotate(x);}}else {if (p == right[fa[p]]) {if (x == right[p]) {leftrotate(p);leftrotate(x);}else {rightrotate(x);leftrotate(x);}}else {if (x == right[p]) {leftrotate(x);rightrotate(x);}else {rightrotate(p);rightrotate(x);}}}} } inline void acc(int x) {int y = 0;while (x) {splay(x);right[x] = y;pushup(x);y = x;x = fa[x];} } inline void make_root(int x) {acc(x);splay(x);rev[x] = !rev[x]; } inline void joyn(int x, int y) {make_root(x);fa[x] = y;splay(x); } inline void cutt(int x, int y) {make_root(x);acc(y);splay(y);left[y] = fa[x] = 0;pushup(y); }int main(void) {//freopen("in.txt", "r", stdin);scanf("%d", &n);root = n + 1;for (int i = 1; i <= n; ++i) {scanf("%d", &t2);t2 = i + t2 < root? i + t2: root;siz[i] = 1;fa[i] = ori_tree_fa[i] = t2;}siz[root] = 1;scanf("%d", &m);while (m--) {scanf("%d%d", &t1, &t2);++t2;if (t1 == 1) {make_root(root);acc(t2);splay(t2);printf("%d\n", siz[left[t2]]);}else {scanf("%d", &t3);t3 = t2 + t3 < root? t2 + t3: root;cutt(t2, ori_tree_fa[t2]);joyn(t2, t3);ori_tree_fa[t2] = t3;}}return 0; }

　　我說的那個智障bug是指，splay開時前，pushdown那里，我錯寫成了

for (int i = x; !isroot(i); i = fa[i]) {stk[top++] = i; }

　　被這個弄了好久。

轉(zhuǎn)載于:https://www.cnblogs.com/ciao-sora/p/6097512.html

總結(jié)

以上是生活随笔為你收集整理的bzoj2002 [Hnoi2010]Bounce 弹飞绵羊【LCT】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。