【题解】可持久化文艺平衡树

第一篇黑题题解，也是第一篇模板题题解，有点小激动

题目内容

=>传送门

解法

思路

就是用FHQ Treap打标记完成区间反转，复制节点完成可持久化

为了保证每次操作对历史版本不产生影响，在PushDown()和Split()的操作时复制节点。因为每次Merge()前都会Split()，所以Merge()时就不需要复制节点了。

还有，记得开long long

代码

#include <iostream>

using namespace std;
typedef long long LL;

const int MAXN = 2e5 + 5;
const int INF = 1e9 + 7;

int Rand() {
    static LL seed = 0x131309d;
    return seed = ((seed * 233333LL) ^ 12345678LL) % INF;
}

struct Node{
    int val, pri, siz;
    bool tag;
    LL sum;
    Node *ch[2];

    Node(int val = 0) : val(val) {
        pri = Rand();
        siz = 1;
        sum = val;
        ch[0] = ch[1] = NULL;
        tag = false;
    }
};

Node *rt[MAXN];
int n, m;
LL cur;

Node *Copy(Node *now) {
    Node *ret = new Node;
    if (now) *ret = *now;
    return ret;
}

void Update(Node *now) {
    now->siz = (LL)(now->ch[0] ? now->ch[0]->siz : 0) + (LL)(now->ch[1] ? now->ch[1]->siz : 0) + 1;
    now->sum = (LL)(now->ch[0] ? now->ch[0]->sum : 0) + (LL)(now->ch[1] ? now->ch[1]->sum : 0) + (LL)now->val;
}

void PushDown(Node *now) {
    if (!now->tag) return;
    swap(now->ch[0], now->ch[1]);
    if (now->ch[0]) {
        now->ch[0] = Copy(now->ch[0]);
        now->ch[0]->tag ^= 1;
    }
    if (now->ch[1]) {
        now->ch[1] = Copy(now->ch[1]);
        now->ch[1]->tag ^= 1;
    }
    now->tag = false;
}

void Split(Node *now, int k, Node *&l, Node *&r) {
    if (!now) {
        l = r = NULL;
        return;
    }
    PushDown(now);
    int ls = now->ch[0] ? now->ch[0]->siz : 0;
    if (k <= ls) {
        r = Copy(now);
        Split(r->ch[0], k, l, r->ch[0]);
        Update(r);
    } else {
        l = Copy(now);
        Split(l->ch[1], k - ls - 1, l->ch[1], r);
        Update(l);
    }
}

Node *Merge(Node *a, Node *b) {
    if (!a || !b) return a ? a : b;
    if (a->pri <= b->pri) {
        PushDown(b);
        b->ch[0] = Merge(a, b->ch[0]);
        Update(b);
        return b;
    } else {
        PushDown(a);
        a->ch[1] = Merge(a->ch[1], b);
        Update(a);
        return a;
    }
}

void Insert(Node *&root, int k, int val) {
    Node *a, *b;
    Split(root, k, a, b);
    root = Merge(a, Merge(new Node(val), b));
}

void Remove(Node *&root, int pos) {
    Node *a, *b, *c, *d;
    Split(root, pos, d, c);
    Split(d, pos - 1, a, b);
    if (b) delete b;
    root = Merge(a, c);
}

void Reverse(Node *&root, int l, int r) {
    Node *a, *b, *c, *d;
    Split(root, r, d, c);
    Split(d, l - 1, a, b);
    if (b) b->tag ^= 1;
    root = Merge(a, Merge(b, c));
}

LL Query(Node* &root, int l, int r) {
    Node *a, *b, *c, *d;
    Split(root, r, d, c);
    Split(d, l - 1, a, b);
    LL ans = b ? b->sum : 0LL;
    root = Merge(a, Merge(b, c));
    return ans;
}

void Init() {
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    cur = 0LL;
}

void Work() {
    int op, ver;
    LL p, x, l, r;
    for (int i = 1; i <= n; i++) {
        cin >> ver >> op;
        rt[i] = rt[ver];
        if (op == 1) {
            cin >> p >> x;
            p ^= cur; x ^= cur;
            Insert(rt[i], p, x);
        } else if (op == 2) {
            cin >> p;
            p ^= cur;
            Remove(rt[i], p);
        } else if (op == 3) {
            cin >> l >> r;
            l ^= cur; r ^= cur;
            Reverse(rt[i], l, r);
        } else {
            cin >> l >> r;
            l ^= cur; r ^= cur;
            cur = Query(rt[i], l, r);
            cout << cur << endl;
        }
    }
}

int main() {
    Init();
    Work();
    return 0;
}

版权属于：Noire02

本文链接：https://noire02.moe/archives/P5055.html

北京第三区交通委提醒您：复制千万条，版权第一条。转载删出处，博主两行泪。