P1001 A+B Problem

P1001 A+B Problem 题解。

众所周知有很多种方法能 AC 这道题，于是我们先用普通 Treap 来做一下：

#include <iostream>
#include <random>
using namespace std;
const int N = 5;
int a, b, rt, cnt;
mt19937 rng(random_device{}());
struct node {
    int l, r, val, sum, cnt, siz;
    mt19937::result_type key;
} tree[N];
void maintain(int rt) {
    tree[rt].siz = tree[tree[rt].l].siz + tree[tree[rt].r].siz + tree[rt].cnt;
    tree[rt].sum = tree[tree[rt].l].sum + tree[tree[rt].r].sum + tree[rt].cnt * tree[rt].val;
}
pair<int, int> split(int rt, int k) {
    if (!rt) return {};
    if (tree[rt].val >= k) {
        auto [l, r] = split(tree[rt].l, k);
        tree[rt].l = r;
        maintain(rt);
        return {l, rt};
    } else {
        auto [l, r] = split(tree[rt].r, k);
        tree[rt].r = l;
        maintain(rt);
        return {rt, r};
    }
}
int merge(int lt, int rt) {
    if (!lt || !rt) return lt + rt;
    if (tree[lt].key < tree[rt].key) {
        tree[lt].r = merge(tree[lt].r, rt);
        maintain(lt);
        return lt;
    } else {
        tree[rt].l = merge(lt, tree[rt].l);
        maintain(rt);
        return rt;
    }
}
void insert(int k) {
    auto [l, p] = split(rt, k);
    auto [m, r] = split(p, k + 1);
    if (m) tree[m].sum += k, ++tree[m].cnt, ++tree[m].siz;
    else tree[m = ++cnt] = {0, 0, k, k, 1, 1, rng()};
    rt = merge(merge(l, m), r);
}
int query(int x, int y) {
    auto [l, p] = split(rt, x);
    auto [m, r] = split(p, y + 1);
    int res = tree[m].sum;
    rt = merge(merge(l, m), r);
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> a >> b;
    insert(a);
    insert(b);
    cout << query(-1e9, 1e9);
    return 0;
}

但是用这种普通 Treap 还是太没意思了啊。

于是我们就想到可以把 split 作为减法，merge 作为加法。

这样我们就写出了一棵值域 Treap！（bushi

#include <iostream>
#include <random>
using namespace std;
int a, b;
mt19937 rng(random_device{}());
int lson(int rt) { return (rt - 1) >> 1; }
int rson(int rt) { return (rt - 1) - ((rt - 1) >> 1); }
int maintain(int ls, int rs) { return ls + rs + 1; }
pair<int, int> split(int rt, int x) {
    if (!rt) return {};
    int ls = lson(rt), rs = rson(rt);
    if (ls >= x) {
        auto [l, r] = split(ls, x);
        return {l, maintain(r, rs)};
    } else {
        auto [l, r] = split(rs, x - ls - 1);
        return {maintain(ls, l), r};
    }
}
int merge(int lt, int rt) {
    if (!lt || !rt) return lt + rt;
    if (rng() & 1) {
        int ls = lson(lt), rs = rson(lt);
        return maintain(ls, merge(rs, rt));
    } else {
        int ls = lson(rt), rs = rson(rt);
        return maintain(merge(lt, ls), rs);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> a >> b;
    if (a >= 0 && b >= 0) cout << merge(a, b);
    else if (a >= 0 && b < 0) {
        if (a >= -b) cout << split(a, -b).second;
        else cout << -split(-b, a).second;
    } else if (a < 0 && b >= 0) {
        if (b >= -a) cout << split(b, -a).second;
        else cout << -split(-a, b).second;
    } else cout << -merge(-a, -b);
    return 0;
}