欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

经验总结

拒绝压行,从我做起(大雾)。

有时间再填坑吧