CSES 2074：Reversals and Sums

CSES 2074：Reversals and Sums

題目大意：給你一個 $1\sim n$ 的陣列，有兩種操作，一種是將區間 $l\sim r$ 反轉，一種是計算區間 $l\sim r$ 總和。

解法：我被 $\text{Treap}$ 揍爛…。

$\text{Code：}$

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

#define LL long long
#define null NULL

const int INF = 2e9;

mt19937 seed (time (null));

int rnd() {
    return uniform_int_distribution<int> (0, INF) (seed);
}

struct Node {
    int siz = 1, prior = rnd(), val;
    LL sum;
    bool rev = 0;
    Node *l = null, *r = null;
    Node() {}
    Node (int val) : sum (val), val (val) {}
};

int siz (Node *node) {
    return node == null ? 0 : node->siz;
}

LL sum (Node *node) {
    return node == null ? 0 : node->sum;
}

void push_up (Node *node) {
    node->siz = siz (node->l) + siz (node->r) + 1;
    node->sum = sum (node->l) + sum (node->r) + node->val;
}

void push_down (Node *node) {
    if (node->rev) {
        node->rev = 0;
        swap (node->l, node->r);
        if (node->l != null)
            node->l->rev ^= 1;
        if (node->r != null)
            node->r->rev ^= 1;
    }
}

Node *Merge (Node *a, Node *b) {
    if (a == null)
        return b;
    if (b == null)
        return a;
    if (a->prior < b->prior) {
        push_down (b);
        b->l = Merge (a, b->l);
        push_up (b);
        return b;
    } else {
        push_down (a);
        a->r = Merge (a->r, b);
        push_up (a);
        return a;
    }
}

void Split (Node *node, Node *&a, Node *&b, int k) {
    if (node == null) {
        a = b = null;
        return;
    }
    push_down (node);
    if (siz (node->l) >= k) {
        b = node;
        Split (node->l, a, b->l, k);
        push_up (b);
    } else {
        a = node;
        Split (node->r, a->r, b, k - siz (node->l) - 1);
        push_up (a);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    Node *root = null;
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        root = Merge (root, new Node (val));
    }

    while (m--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            Node *t1, *t2;
            Split (root, t1, root, l - 1);
            Split (root, root, t2, r - l + 1);
            root->rev ^= 1;
            root = Merge (Merge (t1, root), t2);
        } else {
            Node *t1, *t2;
            Split (root, t1, root, l - 1);
            Split (root, root, t2, r - l + 1);
            cout << root->sum << '\n';
            root = Merge (Merge (t1, root), t2);
        }
    }
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

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