一道傻逼 LCT ,结果调了好久。

首先直接离线处理,发现询问在中间做和在最后做是一样的,相当于一棵一棵树扫过去用 LCT 动态维护一个区间换父亲的操作,考虑用 LCT 建虚点,搞一搞即可。

需要注意这题查询两点间的距离的时候不能直接 split 出来,因为 LCT 上的 LCA 有可能是虚点,从而忽略了虚 LCA 到实 LCA 中间一段距离对答案的贡献。同时还注意点小细节,比如 1 号点的范围 233 .

另外这题保证了操作合法,就没必要费力不讨好的每次都 get_root 一下了,否则可能会 TLE 飞 。。。

关于如何求 LCT 上的 LCA :对于 \operatorname{access} 操作保存下最后一次的 \operatorname{splay}y 。先 \operatorname{makeroot}(root) ,再 \operatorname{access}(u) ,最后 \operatorname{access}(v) 返回的值就是答案。

代码:

// =================================
//   author: memset0
//   date: 2019.03.28 18:26:24
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define debug(...) ((void)0)
#ifndef debug
#define debug(...) fprintf(stderr,__VA_ARGS__)
#endif
namespace ringo {
template <class T> inline void read(T &x) {
    x = 0; register char c = getchar(); register bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}
template <class T> inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 4e5 + 10;
int n, m, cnt, lst, nod, ans[N], ql[N], qr[N], qid[N], qnd[N], qrt[N], rst[N], rnd[N], rtd[N];
std::vector <int> nodS[N], nodE[N], rotS[N], rotE[N];

struct query {
    int opt, l, r, x;
} q[N];
std::vector <query> qry[N];

inline void print(std::string name, std::vector <int> vet) {
    std::cout << name << " :";
    for (auto i : vet) std::cout << " " << i;
    std::cout << std::endl;
}

struct link_cut_tree {
    int sum[N], tag[N], ch[N][2], fa[N], rev[N];
#define get_son(x) (ch[fa[x]][1] == (x))
#define is_root(x) (ch[fa[x]][0] != (x) && ch[fa[x]][1] != (x))
#define maintain(x) sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + tag[x]
    inline void rotate(int x) {
        if (!x || !fa[x]) return;
        int f = fa[x], ff = fa[f], fs = get_son(x), ffs = get_son(f), y = ch[x][fs ^ 1];
        if (!is_root(f)) ch[ff][ffs] = x; ch[x][fs ^ 1] = f, ch[f][fs] = y;
        fa[y] = f, fa[f] = x, fa[x] = ff, maintain(f), maintain(x);
    }
    inline void pushup(int x) { rev[x] ^= 1, std::swap(ch[x][0], ch[x][1]); }
    inline void pushdown(int x) { if (rev[x]) pushup(ch[x][0]), pushup(ch[x][1]), rev[x] = 0; }
    inline void clean_up(int x) { if (!is_root(x)) clean_up(fa[x]); pushdown(x); }
    inline void splay(int x) {
        clean_up(x);
        for (int f = fa[x]; !is_root(x); rotate(x), f = fa[x])
            if (!is_root(f)) rotate(get_son(f) == get_son(x) ? f : x);
        maintain(x);
    }
    inline int access(int x) {
        int y = 0;
        while (x) {
            splay(x), ch[x][1] = y, maintain(x);
            y = x, x = fa[x];
        }
        return y;
    }
    inline void make_root(int x) { access(x), splay(x), pushup(x); }
    inline void split(int x, int y) { make_root(x), access(y), splay(y); }
    inline int get_root(int x) { access(x), splay(x); while (ch[x][0]) x = ch[x][0]; return x; }
    inline void link(int x, int y) {
        // printf("link %d %d\n", x, y);
        // if (get_root(x) != get_root(y)) {
            make_root(x), fa[x] = y, maintain(y);
        // }
    }
    inline void cut(int x, int y) {
        // printf("cut %d %d\n", x, y);
        // if (get_root(x) == get_root(y)) {
            split(x, y);
            // printf(">>> %d %d %d\n", ch[x][1], fa[x], y, ch[y][0], x);
            // if (!ch[x][1] && fa[x] == y && ch[y][0] == x)
                fa[x] = ch[y][0] = 0, maintain(y);
        // }
    }
    void dfs(int u) {
        if (!u) return;
        dfs(ch[u][0]);
        printf("[%d] ", u, tag[u]);
        dfs(ch[u][1]);
    }
    inline int query(int u, int v) {
        // if (get_root(u) != get_root(v)) { return -1; }
        // printf("query %d %d\n", u, v);
        int w, dis = 0;
        make_root(1), access(u), w = access(v);
        // printf("query %d %d %d\n", u, v, w);
        access(u), splay(u), dis += sum[u];
        // printf("u[%d] : %d %d : %d %d %d\n", u, sum[u], tag[u], fa[u], ch[u][0], ch[u][1]), dfs(u), puts("");
        access(v), splay(v), dis += sum[v];
        // printf("v[%d] : %d %d : %d %d %d\n", v, sum[v], tag[v], fa[v], ch[v][0], ch[v][1]), dfs(v), puts("");
        access(w), splay(w), dis -= (sum[w] << 1);
        // printf("w[%d] : %d %d : %d %d %d\n", w, sum[w], tag[w], fa[w], ch[w][0], ch[w][1]), dfs(w), puts("");
        return dis;
    }
} lct;

void main() {
    read(n), read(m);
    for (int i = 1, u, v, l, r, x, opt; i <= m; i++)
        switch (read(opt), opt) {
            case 0: read(l), read(r), q[i] = (query){opt, l, r, -1}, ++cnt; break;
            case 1: read(l), read(r), read(x), q[i] = (query){opt, l, r, x}; break;
            case 2: read(x), read(u), read(v), q[i] = (query){opt, u, v, x}; break;
        }
    for (int i = 1; i <= cnt + 1; i++) lct.tag[i] = lct.sum[i] = 1;
    nod = ++cnt, cnt = 1, lst = ++nod, ql[1] = 1, qr[1] = n, lct.link(lst, 1);
    for (int i = 1; i <= m; i++)
        if (q[i].opt == 0) {
            ++cnt, ql[cnt] = q[i].l, qr[cnt] = q[i].r, qid[cnt] = i, qnd[i] = cnt, qrt[i] = lst;
            nodS[q[i].l].push_back(i), nodE[q[i].r].push_back(i);
        } else if (q[i].opt == 1) {
            q[i].l = std::max(q[i].l, ql[q[i].x]), q[i].r = std::min(q[i].r, qr[q[i].x]);
            if (q[i].l > q[i].r) continue;
            rst[i] = lst, rnd[i] = ++nod, rtd[i] = q[i].x, lct.link(nod, lst), lst = nod;
            rotS[q[i].l].push_back(i), rotE[q[i].r].push_back(i);
        } else {
            qry[q[i].x].push_back((query){3, q[i].l, q[i].r, i});
        }
    for (int u = 1; u <= n; u++) {
        // printf("=== %d ===\n", u);
        // print("rotS", rotS[u]);
        // print("nodE", nodE[u]);
        // print("rotE", rotE[u]);
        for (int i : nodS[u]) lct.link(qnd[i], qrt[i]);
        for (int i : rotS[u]) lct.cut(rnd[i], rst[i]), lct.link(rnd[i], rtd[i]);
        for (auto &it : qry[u]) ans[it.x] = lct.query(it.l, it.r);
        for (int i : rotE[u]) lct.cut(rnd[i], rtd[i]), lct.link(rnd[i], rst[i]);
        for (int i : nodE[u]) lct.cut(qnd[i], qrt[i]);
    }
    for (int i = 1; i <= m; i++) if (q[i].opt == 2) print(ans[i], '\n');
}

} signed main() { return ringo::main(), 0; }

data maker:

// =================================
//   author: memset0
//   date: 2019.03.29 15:28:32
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define debug(...) ((void)0)
#ifndef debug
#define debug(...) fprintf(stderr,__VA_ARGS__)
#endif
namespace ringo {
template <class T> inline void read(T &x) {
    x = 0; register char c = getchar(); register bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}
template <class T> inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

template <class T> T rand_from_set(std::set <T> set) {
    auto it = set.begin();
    int walker = rand() % set.size();
    while (walker--) ++it;
    return *it;
}

void main() {
    srand(time(0) ^ clock());
    int n = rand() % 5 + 1;
    int m = rand() % 10 + 1;
    int cnt = 1;
    printf("%d %d\n", n, m);
    std::vector <std::set <int> > set(n + 1);
    for (int i = 1; i <= n; i++)
        set[i].insert(1);
    for (int i = 1; i <= m; i++) {
        int opt = rand() % 3;
        if (opt == 0) {
            int l = rand() % n + 1;
            int r = rand() % n + 1;
            if (l > r) std::swap(l, r);
            printf("%d %d %d\n", opt, l, r), ++cnt;
            for (int i = l; i <= r; i++)
                set[i].insert(cnt);
        } else if (opt == 1) {
            int l = rand() % n + 1;
            int r = rand() % n + 1;
            if (l > r) std::swap(l, r);
            printf("%d %d %d %d\n", opt, l, r, rand() % cnt + 1);
        } else {
            int x = rand() % n + 1;
            int u = rand_from_set(set[x]);
            int v = rand_from_set(set[x]);
            printf("%d %d %d %d\n", opt, x, u, v);
        }
    }
}

} signed main() { return ringo::main(), 0; }

LCT

已有 2 条评论

  1. 然而我并不会做这题/kel

  2. 哇,超级喜欢您的LCT模板啊~ 顺便data maker我也收了(雾)

UOJ345 【清华集训2017】榕树之心
上一篇 «
UOJ269 【清华集训2016】如何优雅地求和
» 下一篇