LCT维护子树中的疑惑
  • 板块学术版
  • 楼主Engulf
  • 当前回复15
  • 已保存回复15
  • 发布时间2023/7/20 14:11
  • 上次更新2023/11/3 08:40:10
查看原帖
LCT维护子树中的疑惑
482728
Engulf楼主2023/7/20 14:11

对于这样的一道题目

给定一棵大小为 nn 的有根点权树,要求支持以下操作: 换根 | 单点修改 | 查询子树最小值

我参考的是网上 LCT + set 维护虚子树的做法,我有几点疑惑:

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

const int N = 1e5 + 5, inf = 2e9;

int n, q;

int son[N][2], fa[N];
int val[N];
int chain[N], sub[N];
int mn[N];
int rev[N];

int root;

multiset<int> vtree[N];

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

void pushup(int x) {
    chain[x] = mn[x] = val[x], sub[x] = inf;  
    chain[x] = min({chain[x], chain[son[x][0]], chain[son[x][1]]}); 
    sub[x] = min({sub[son[x][0]], sub[son[x][1]], *vtree[x].begin()}); 
    mn[x] = min(chain[x], sub[x]);
}

void pushrev(int x) {swap(son[x][0], son[x][1]), rev[x] ^= 1;}

void pushdown(int x) {
    if (!rev[x]) return;
    if (son[x][0]) pushrev(son[x][0]);
    if (son[x][1]) pushrev(son[x][1]);
    rev[x] ^= 1;
}

void pushall(int x) {
    if (!isroot(x)) pushall(fa[x]);
    pushdown(x);
}

void rotate(int x) {
    int y = fa[x], z = fa[y];
    int k = son[y][1] == x;
    if (!isroot(y)) son[z][son[z][1] == y] = x;
    fa[x] = z;
    son[y][k] = son[x][k ^ 1], fa[son[x][k ^ 1]] = y;
    son[x][k ^ 1] = y, fa[y] = x;
    pushup(y), pushup(x);
}

void splay(int x) {
    pushall(x);
    while (!isroot(x)) {
        int y = fa[x], z = fa[y];
        if (!isroot(y)) rotate(son[z][1] == y ^ son[y][1] == x ? x : y);
        rotate(x);
    }
}

void access(int x) {
    for (int y = 0; x; x = fa[y = x]) {
        splay(x);
        if (y) vtree[x].erase(vtree[x].lower_bound(mn[y]));
        if (son[x][1]) vtree[x].insert(mn[son[x][1]]);
        son[x][1] = y, pushup(x);
    }
}

void makeroot(int x) {
    access(x);
    splay(x);
    pushrev(x);
}

void link(int x, int y) {
    makeroot(x);
    fa[x] = y;
    vtree[y].insert(mn[x]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    mn[0] = chain[0] = sub[0] = val[0] = inf;
    for (int i = 0; i <= n; i++) vtree[i].insert(inf);
    for (int i = 1; i <= n; i++) {
        int f;
        cin >> f >> val[i];
        if (!f) root = i;
        else link(f, i);
    }
    makeroot(root);
    while (q--) {
        char op;
        int x, y;
        cin >> op >> x;
        if (op == 'V') cin >> y, access(x), splay(x), val[x] = y;
        if (op == 'E') makeroot(root = x);
        if (op == 'Q') access(x), splay(x), cout << min(val[x], *vtree[x].begin()) << "\n";
    }
    return 0;
}
  1. 单点修改不能直接把 xx splay 到当前 splay 的根节点进行修改吗?为什么需要 access(不这样样例都过不去)再修改。
  2. query 不是很明白为什么 access(x) + splay(x) 后就能得到 xx 的子树了。
2023/7/20 14:11
加载中...