TIOJ 2124：殿壬看蝴蝶

TIOJ 2124：殿壬看蝴蝶

題目大意：這裡。

解法：我們會用到 $\text{Treap}$ 跟 $\text{BIT}$，這裡的 $\text{Treap}$ 需要支援一種操作，就是給你指標，請你輸出他在陣列第幾個，可以對每個節點存它的父節點，然後就可以用一個 $\text{rk}$ 的函式，就可以 $\text{AC}$ 這題了。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define TIOJQQ ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

mt19937 seed (time (NULL));
#define rnd(l,r) uniform_int_distribution<int>(l,r)(seed)

const int SIZE = 2e5 + 5;

int n, q;
int a[SIZE];

struct Treap {
    int id, sum = 0, siz = 1, prior = rnd (0, 2e9);
    Treap *fa = NULL, *ls = NULL, *rs = NULL;
    Treap() {}
    Treap (int id) : id (id), sum (a[id]) {}
};

int siz (Treap *t) {
    return t ? t->siz : 0;
}

int sum (Treap *t) {
    return t ? t->sum : 0;
}

void Pull (Treap *t) {
    t->siz = siz (t->ls) + siz (t->rs) + 1;
    t->sum = sum (t->ls) + sum (t->rs) + a[t->id];
    if (t->ls) t->ls->fa = t;
    if (t->rs) t->rs->fa = t;
}

Treap *Merge (Treap *a, Treap *b) {
    if (!a || !b) return a ? a : b;
    if (a->prior > b->prior) {
        a->rs = Merge (a->rs, b);
        Pull (a);
        return a;
    } else {
        b->ls = Merge (a, b->ls);
        Pull (b);
        return b;
    }
}

void Split (Treap *t, Treap *&a, Treap *&b, int k) {
    if (!t) {
        a = b = NULL;
        return;
    }
    if (k <= siz (t->ls)) {
        b = t;
        Split (t->ls, a, b->ls, k);
        Pull (b);
    } else {
        a = t;
        Split (t->rs, a->rs, b, k - siz (t->ls) - 1);
        Pull (a);
    }
}

int rk (Treap *t, bool isl = 0) {
    int re = (isl ? 0 : siz (t->ls) + 1);
    if (t->fa == NULL) return re;
    if (t->fa->ls == t) return re + rk (t->fa, 1);
    return re + rk (t->fa, 0);
}

Treap *to[SIZE], *root = NULL;
int bit[SIZE];

void update (int pos, int x) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += x;
}

int query (int pos) {
    int re = 0;
    for (; pos; pos -= pos & -pos) re += bit[pos];
    return re;
}

void Swap (int l1, int r1, int l2, int r2) {
    Treap *t1, *t2, *t3, *t4;
    Split (root, root, t4, r2);
    Split (root, root, t3, l2 - 1);
    Split (root, t2, root, r1);
    Split (t2, t1, t2, l1 - 1);
    root = Merge (Merge (Merge (t1, t3), root), Merge (t2, t4));
}

void Change (int i, int w) {
    Treap *t1, *t2;
    Split (root, root, t2, i);
    Split (root, t1, root, i - 1);
    int id = root->id;
    update (id, w - a[id]);
    a[id] = w;
    root->sum = w;
    root = Merge (Merge (t1, root), t2);
}

void solve() {
    cin >> n >> q;
    FOR (i, 1, n) {
        cin >> a[i];
        to[i] = new Treap (i);
        root = Merge (root, to[i]);
        update (i, a[i]);
    }
    while (q--) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int i, j;
            cin >> i >> j;
            i = rk (to[i]), j = rk (to[j]);
            if (i > j) swap (i, j);
            Swap (i, i, j, j);
        }
        if (ty == 2) {
            int i, j;
            cin >> i >> j;
            if (i > j) swap (i, j);
            Swap (i, i, j, j);
        }
        if (ty == 3) {
            int i, w;
            cin >> i >> w;
            Change (rk (to[i]), w);
        }
        if (ty == 4) {
            int i, w;
            cin >> i >> w;
            Change (i, w);
        }
        if (ty == 5) {
            int l1, r1, l2, r2;
            cin >> l1 >> r1 >> l2 >> r2;
            if (l1 > l2) {
                swap (l1, l2);
                swap (r1, r2);
            }
            Swap (l1, r1, l2, r2);
        }
        if (ty == 6) {
            int i;
            cin >> i;
            Treap *t1, *t2;
            Split (root, t1, root, i - 1);
            Split (root, root, t2, 1);
            cout << root->id << '\n';
            root = Merge (Merge (t1, root), t2);
        }
        if (ty == 7) {
            int i;
            cin >> i;
            cout << rk (to[i]) << '\n';
        }
        if (ty == 8) {
            int l, r;
            cin >> l >> r;
            cout << query (r) - query (l - 1) << '\n';
        }
        if (ty == 9) {
            int l, r;
            cin >> l >> r;
            Treap *t1, *t2;
            Split (root, root, t2, r);
            Split (root, t1, root, l - 1);
            cout << root->sum << '\n';
            root = Merge (Merge (t1, root), t2);
        }
    }
}

int main() {
    TIOJQQ;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！