Lxzyzby Lxzyzby

Luogu P4847 银河英雄传说V2

in FHQ Treap,Link-Cut-Tree read (45) 文章转载请注明来源!

题目链接

LinkCutTree

每一个权值都是一个点,构造一颗动态树,支持寻找链头,链尾的操作,维护 $sum$ 即可,

注:因为是一条链所以不能使用makeroot

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5;
#define int long long
struct LinkCutTree {
    int val[MAXN], fa[MAXN], siz[MAXN], rev[MAXN];
    int st[MAXN], sum[MAXN], ch[MAXN][2];
    bool nroot(int x) {
        return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
    }
    void Rev(int x) {
        swap(ch[x][0], ch[x][1]);
        rev[x] ^= 1;
    }
    void PushUp(int x) {
        siz[x] = 1; sum[x] = val[x];
        if(ch[x][0]) siz[x] += siz[ch[x][0]], sum[x] += sum[ch[x][0]];
        if(ch[x][1]) siz[x] += siz[ch[x][1]], sum[x] += sum[ch[x][1]];
    }
    void PushDown(int x) {
        if(rev[x]) {
            Rev(ch[x][0]);
            Rev(ch[x][1]);
            rev[x] ^= 1;
        }
    }
    void rotate(int x) {
        int y = fa[x], z = fa[y], k = ch[y][1] == x, w = ch[x][!k];
        if(nroot(y)) ch[z][ch[z][1]==y] = x;
        ch[x][!k] = y; ch[y][k] = w;
        if(w) fa[w] = y;
        fa[x] = z; fa[y] = x;
        PushUp(y); PushUp(x);
    }
    void Splay(int x) {
        int top = 0, y = x; st[++top] = y;
        while(nroot(y)) st[++top] = fa[y], y = fa[y];
        while(nroot(x)) {
            int y = fa[x], z = fa[y];
            if(nroot(y)) rotate((ch[z][1]==y)^(ch[y][1]==x) ? x : y);
            rotate(x);
        }
        PushUp(x);
    }
    int find(int x, int opt) {
        Splay(x); 
        while(ch[x][opt]) PushDown(x), x = ch[x][opt];
        Splay(x); return x;
    }
    void access(int x) {
        for(int y = 0; x; y = x, x = fa[x])
            Splay(x), ch[x][1] = y, PushUp(x);
    }
    void link(int x, int y) {
        int L = find(y, 1);
        if(L == find(x, 1)) return;
        int R = find(x, 0);
        Splay(L); fa[R] = L;
        access(find(x, 1));
    }
    void cut(int x) {
        Splay(x); ch[x][0] = fa[ch[x][0]] = 0; PushUp(x);
    }
    int Query(int x, int y) {
        if(find(x, 0) != find(y, 0)) return -1;
        int ans = 0;
        Splay(x); ans -= sum[ch[x][0]];
        Splay(y); ans += sum[ch[y][0]] + val[y];
        if(ans <= 0) {
            ans = 0;
            Splay(y); ans -= sum[ch[y][0]];
            Splay(x); ans += sum[ch[x][0]] + val[x];
        }
        return ans;
    }
}t;
int n, m, val[MAXN];
void SubtaskM() {
    int x, y; cin >> x >> y;
    t.link(x, y);
}
void SubtaskD() {
    int x; cin >> x;
    t.cut(x);
}
void SubtaskQ() {
    int x, y; cin >> x >> y;
    cout << t.Query(x, y) << endl;
}
int32_t main() {
    #ifdef ONLINE_JUDGE
    #else
        freopen("input","r",stdin);
    #endif
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        t.val[i] = x;
    }
    for(int i = 1; i <= m; i++) {
        char opt[10]; cin >> opt;
        if(opt[0] == 'M') SubtaskM();
        if(opt[0] == 'D') SubtaskD();
        if(opt[0] == 'Q') SubtaskQ();
    }
    return 0;
}
FHQ Treap

每一个权值都是一颗平衡树,相互合并即可,注意的是,在分裂之后,需要手动把两个分裂出来的结点,父亲 $fa[rt1] \ fa[rt2]$ 清空

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 5e5;
#define int long long
mt19937 Rand(time(0));
struct FHQ_Treap {
    int fa[MAXN], val[MAXN], siz[MAXN], rnd[MAXN], ls[MAXN], rs[MAXN];
    int root, cnt, id[MAXN], sum[MAXN];
    int newNode(int x, int rk) {
        val[++cnt] = x; siz[cnt] = 1; rnd[cnt] = Rand(); 
        fa[cnt] = ls[cnt] = rs[cnt] = 0; id[rk] = cnt; sum[cnt] = x;
        return cnt;
    }
    void PushUp(int rt) {
        siz[rt] = 1; sum[rt] = val[rt];
        if(ls[rt]) siz[rt] += siz[ls[rt]], sum[rt] += sum[ls[rt]], fa[ls[rt]] = rt;
        if(rs[rt]) siz[rt] += siz[rs[rt]], sum[rt] += sum[rs[rt]], fa[rs[rt]] = rt;
    }
    void split(int rt, int C, int &x, int &y) {
        if(!rt) return x = y = 0, void();
        if(siz[ls[rt]] + 1 <= C) x = rt, split(rs[rt], C - siz[ls[rt]] - 1, rs[rt], y);
        else y = rt, split(ls[rt], C, x, ls[rt]);
        PushUp(rt);
    }
    int merge(int x, int y) {
        if(!x || !y) return x + y;
        if(rnd[x] < rnd[y]) return rs[x] = merge(rs[x], y), PushUp(x), x;
        else return ls[y] = merge(x, ls[y]), PushUp(y), y;
    }
    int FindRank(int rt) {
        int res = siz[ls[rt]] + 1;
        while(fa[rt]) {
            if(rs[fa[rt]] == rt) res += siz[ls[fa[rt]]] + 1;
            rt = fa[rt];
        }
        return res;
    }
    int GetStart(int rt) {
        while(fa[rt]) rt = fa[rt];
        return rt;
    }
}t;
void SubtaskM() {
    int x, y; cin >> x >> y;
    int xs = t.GetStart(t.id[x]), ys = t.GetStart(t.id[y]);
    if(xs == ys) return;
    t.merge(ys, xs);
}
void SubtaskD() {
    int x, rt1, rt2; cin >> x;
    t.split(t.GetStart(t.id[x]), t.FindRank(t.id[x])-1, rt1, rt2);
    t.fa[rt1] = t.fa[rt2] = 0;
}
void SubtaskQ() {
    int x, y; cin >> x >> y;
    int xs = t.GetStart(t.id[x]), ys = t.GetStart(t.id[y]);
    if(xs != ys) return cout << -1 << endl, void();
    int sizx = t.FindRank(t.id[x]), sizy = t.FindRank(t.id[y]);
    if(sizx > sizy) swap(x, y), swap(sizx, sizy), swap(xs, ys);
    int rt1, rt2, rt3;
    t.split(xs, sizy, rt1, rt3); t.split(rt1, sizx-1, rt1, rt2);
    cout << t.sum[rt2] << endl;
    t.merge(t.merge(rt1, rt2), rt3);
}
int n, m; 
void Print_Infor() {
    for(int i = 1; i <= n; i++) {
        cout << t.GetStart(t.id[i]) << ' ';
    }
    cout << endl;
    for(int i = 1; i <= n; i++) {
        cout << t.sum[t.GetStart(t.id[i])] << ' ';
    }
    cout << endl;
}
int32_t main() {
    #ifdef ONLINE_JUDGE
    #else
        freopen("input","r",stdin);
    #endif
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x; t.newNode(x, i);
    }

    for(int i = 1; i <= m; i++) {
        char opt[10]; cin >> opt;
        if(opt[0] == 'M') SubtaskM();
        if(opt[0] == 'D') SubtaskD();
        if(opt[0] == 'Q') SubtaskQ();
        // Print_Infor();
    }
    return 0;
}

本文基于《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
文章链接:https://zby.xyz/index.php/archives/85/ (转载时请注明本文出处及文章链接)

FHQ TreapLink-Cut-Tree
发表新评论
博客已萌萌哒运行
© 2020 由 Typecho 强力驱动.Theme by YoDu
PREVIOUS NEXT
雷姆
拉姆