P3348 [ZJOI2016]大森林(Link-cut-tree)

传送门

题解

题面大意:

\(0.\)区间加节点

\(1.\)区间换根

\(2.\)单点询问距离

如果没有\(1\)操作,因为区间加节点都是加在下面,所以我们可以直接把\(n\)棵树压成一棵树,直接询问即可

有\(1\)操作怎么办?

上面挖掘了一点性质,

加节点加在下面,那么我们可以先把节点都加上去,再询问

那么把操作离线,

先按操作位置排序,再按操作排序(\(0,1\)先),再按时间排序

对于\(0,1\)操作都新建节点

\(0\)建实点

\(1\)建虚点

\(0\)操作的点将连向最后的\(1\)操作

默认每个\(1\)操作连向上一个操作(加点直接加在\(1\)下面)

现在唯一的问题即是\(1\)操作

我们想一下\(pos\)转移到\(pos+1\)

由于一些换根操作

树的形态会发生改变

假如一个换根操作\([l,r]\)

\(x\)换到\(y\)

\(l-1\),根是\(x\)

\(l\),根是\(y\)

那么改变的地方就是把在\(x->y\)操作之后接上\(x\)的点,全部接到\(y\)下面

一个一个挪肯定不行

所以需要一个虚点,挪的话只要挪这一个点

如果没有理解,可以想想,哪些点会连向这个虚点?

一定是时间在它之后的点

没换根之前,这些点都会连向\(x\)

那么问题就解决了..

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

template<class T> inline void read(T &x) {

    x = 0; RG char c = getchar(); bool f = 0;

    while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;

    while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();

    x = f ? -x : x;

    return ;

}

template<class T> inline void write(T x) {

    if (!x) {putchar(48);return ;}

    if (x < 0) x = -x, putchar('-');

    int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;

    for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;

}

const int N = 500010;

int ch[N][2], val[N], sum[N], fa[N], tot;

bool isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }

#define get(x) (ch[fa[x]][1] == x)

void pushup(int x) { sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x]; }

void rotate(int x) {

    int y = fa[x], z = fa[y], k = get(x);

    if (!isroot(y)) ch[z][get(y)] = x; fa[x] = z;

    ch[y][k] = ch[x][k ^ 1]; fa[ch[x][k ^ 1]] = y;

    ch[x][k ^ 1] = y; fa[y] = x;

    pushup(y);

}

void splay(int x) {

    while (!isroot(x)) {

        int y = fa[x];

        if (!isroot(y))

            (get(x) ^ get(y)) ? rotate(x) : rotate(y);

        rotate(x);

    }

    pushup(x);

}

int access(int x) {

    int y = 0; for (; x; y = x, x = fa[x]) splay(x), ch[x][1] = y, pushup(x);

    return y;

}

void link(int x, int y) { access(x); splay(x); fa[x] = y; }

void cut(int x) { access(x); splay(x); ch[x][0] = fa[ch[x][0]] = 0; pushup(x); }

void newnode(int x) { val[++tot] = x; sum[tot] = x; }

int L[N], R[N], id[N], len;

struct node {

    int pos, op, x, y;

    bool operator < (const node &z) const {

        return pos == z.pos ?  op < z.op : pos < z.pos;

    }

}q[N];

int ans[N];

int query(int x, int y) {

    int ans = 0, lca;

    access(x), splay(x); ans += sum[x];

    lca = access(y), splay(y), ans += sum[y];

    access(lca), splay(lca), ans -= 2 * sum[lca];

    return ans;

}

int main() {

    int n, m, cnt = 1, last = 2, qs = 0;

    read(n), read(m);

    newnode(1); L[1] = 1, R[1] = n; id[1] = 1;

    newnode(0); link(2, 1);

    for (int i = 1; i <= m; i++) {

        int op; read(op);

        if (!op) {

            int l, r;

            read(l), read(r);

            newnode(1);

            L[++cnt] = l, R[cnt] = r, id[cnt] = tot;

            q[++len] = (node) {1, i - m, tot, last};

        }

        else if (op == 1) {

            int l, r, x;

            read(l), read(r), read(x);

            l = max(l, L[x]), r = min(r, R[x]);

            if (l <= r) {

                newnode(0); link(tot, last);

                q[++len] = (node) {l, i - m, tot, id[x]};

                q[++len] = (node) {r + 1, i - m, tot, last};

                last = tot;

            }

        }

        else {

            int x, u, v;

            read(x), read(u), read(v);

            q[++len] = (node) {x, ++qs, id[u], id[v]};

        }

    }

	sort(q + 1, q + len + 1);

    int j = 1;

    for (int i = 1; i <= n; i++)

        while (i == q[j].pos && j <= len) {

            if (q[j].op <= 0) cut(q[j].x), link(q[j].x, q[j].y);

            else ans[q[j].op] = query(q[j].x, q[j].y);

			j++;

        }

    for (int i = 1; i <= qs; i++) printf("%d\n", ans[i]);

    return 0;

}

巴特西

P3348 [ZJOI2016]大森林(Link-cut-tree)

题解

Code

最新文章

热门文章