LCT经验总结
程序员文章站
2022-07-02 22:32:49
~~妈妈,我终于会写LCT了!~~ LCT太神奇了,它和Splay能完美结合。在$O(nlogn)$的时间内解决动态树问题。 BZOJ2049 [Sdoi2008]Cave 洞穴勘测 丢板子,懒得解释。用维护一下联通块就行了,因为数据水,并查集也可以水过。 AC代码: c++ include inc ......
妈妈,我终于会写LCT了!
LCT太神奇了,它和Splay能完美结合。在$O(nlogn)$的时间内解决动态树问题。
BZOJ2049 [Sdoi2008]Cave 洞穴勘测
丢板子,懒得解释。用维护一下联通块就行了,因为数据水,并查集也可以水过。
AC代码:
#include <iostream> #include <cstdio> #define ls ch[0] #define rs ch[1] #define lson s[x].ls #define rson s[x].rs #define father s[x].fa const int MAXN = 10000; using namespace std; inline int read() { int x = 0, w = 1; char c = ' '; while (c < '0' || c > '9') { c = getchar(); if (c == '-') w = -1; } while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return x * w; } int n = read(), m = read(); class LCT { struct Node { int data, ch[2], fa; bool rev; } s[MAXN + 5]; public : LCT() { top = 0; }//, for (int i = 1; i <= n; ++i) s[i].data = read(); } void PushDown(int x) { if (s[x].rev) { s[lson].rev ^= 1, s[rson].rev ^= 1, swap(lson, rson); s[x].rev ^= 1; } } bool IsRoot(int x); void rotate(int x); void Splay(int x); void access(int x); void MakeRoot(int x); void link(int x, int y); void cut(int x, int y); int find(int x); private : int top, ST[MAXN + 5]; } T; bool LCT::IsRoot(int x) { return s[father].ls != x && s[father].rs != x; } void LCT::rotate(int x) { int y = father, z = s[y].fa, l, r; if (s[y].ls == x) l = 0; else l = 1; r = l ^ 1; if (!IsRoot(y)) if (s[z].ls == y) s[z].ls = x; else s[z].rs = x; father = z, s[y].fa = x, s[ s[x].ch[r] ].fa = y, s[y].ch[l] = s[x].ch[r], s[x].ch[r] = y; } void LCT::Splay(int x) { top = 0, ST[++top] = x; for (int i = x; !IsRoot(i); i = s[i].fa) ST[++top] = s[i].fa; for (int i = top; i; --i) PushDown(ST[i]); while (!IsRoot(x)) { int y = father, z = s[y].fa; if (!IsRoot(y)) if (s[y].ls == x ^ s[z].ls == y) rotate(x); else rotate(y); rotate(x); } } void LCT::access(int x) { for (int last = 0; x; last = x, x = father) Splay(x), rson = last; } void LCT::MakeRoot(int x) { access(x), Splay(x), s[x].rev ^= 1; } void LCT::link(int x, int y) { MakeRoot(x), father = y; } void LCT::cut(int x, int y) { MakeRoot(x), access(y), Splay(y); if (s[y].ls == x) s[y].ls = father = 0; } int LCT::find(int x) { access(x), Splay(x); while (lson) x = lson; return x; } char c[20]; int main() { for (int i = 1; i <= m; ++i) { scanf ("%s", c); int u = read(), v = read(); switch(c[0]) { case 'Q' : if (T.find(u) == T.find(v)) puts("Yes"); else puts("No"); break; case 'D' : T.cut(u, v); break; case 'C' : T.link(u, v); break; } } }
BZOJ3282 Tree
顺便吐槽一下,BZOJ太多题都叫Tree了。又是动态树板子题。是不是动态树都是板子题啊。用一个要上传标记的Splay维护即可。
AC代码:
#include <iostream> #include <cstdio> #define ls ch[0] #define rs ch[1] #define lson s[x].ls #define rson s[x].rs #define father s[x].fa const int MAXN = 3e5; using namespace std; inline int read() { int x = 0, w = 1; char c = ' '; while (c < '0' || c > '9') { c = getchar(); if (c == '-') w = -1; } while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return x * w; } int n = read(), m = read(); class LCT { struct Node { int data, ch[2], fa, val; bool rev; } s[MAXN + 5]; public : LCT() { for (int i = 1; i <= n; ++i) s[i].data = read(); } void PushUp(int x) { s[x].val = s[lson].val ^ s[rson].val ^ s[x].data; } void PushDown(int x) { if (s[x].rev) { s[x].rev ^= 1, s[lson].rev ^= 1, s[rson].rev ^= 1; swap (lson, rson); } } bool IsRoot(int x); void rotate(int x); void Splay(int x); void MakeRoot(int x); void access(int x); void link(int x, int y); void cut(int x, int y); int find(int x); void update(int x, int cnt); int query(int x, int y); private : int top, ST[MAXN + 5]; } T; bool LCT::IsRoot(int x) { return s[father].ls != x && s[father].rs != x; } void LCT::rotate(int x) { int y = father, z = s[y].fa, l, r; if (s[y].ls == x) l = 0; else l = 1; r = l ^ 1; if (!IsRoot(y)) if (s[z].ls == y) s[z].ls = x; else s[z].rs = x; father = z, s[y].fa = x, s[ s[x].ch[r] ].fa = y, s[y].ch[l] = s[x].ch[r], s[x].ch[r] = y; PushUp(y), PushUp(x); } void LCT::Splay(int x) { top = 0, ST[++top] = x; for (int i = x; !IsRoot(i); i = s[i].fa) ST[++top] = s[i].fa; for (int i = top; i; --i) PushDown(ST[i]); while (!IsRoot(x)) { int y = father, z = s[y].fa; if (!IsRoot(y)) if (s[y].ls == x ^ s[z].ls == y) rotate(x); else rotate(y); rotate(x); } } void LCT::access(int x) { for (int last = 0; x; last = x, x = father) Splay(x), rson = last, PushUp(x); } void LCT::MakeRoot(int x) { access(x), Splay(x), s[x].rev ^= 1; } void LCT::link(int x, int y) { MakeRoot(x), father = y; } void LCT::cut(int x, int y) { MakeRoot(x), access(y), Splay(y); if (s[y].ls == x) s[y].ls = father = 0; } int LCT::find(int x) { access(x), Splay(x); while (lson) x = lson; return x; } void LCT::update(int x, int cnt) { access(x), Splay(x), s[x].data = cnt, PushUp(x); } int LCT::query(int x, int y) { MakeRoot(x), access(y), Splay(y); return s[y].val; } int main( ) { for (int i = 1; i <= m; ++i) { int opt = read(), u = read(), v = read(); switch (opt) { case 0 : printf("%d\n", T.query(u, v) ); break; case 1 : if (T.find(u) != T.find(v)) T.link(u, v); break; case 2 : if (T.find(u) == T.find(v)) T.cut(u, v); break; case 3 : T.update(u, v); } } return 0; }
经验总结
拒绝压行,从我做起(大雾)。
有时间再填坑吧