[一本通学习笔记] 平衡树

10143. 「一本通 4.6 例 1」营业额统计

#include <bits/stdc++.h>
using namespace std;

const int N = 2000005;

namespace Splay {
int k[N], fa[N], ch[N][2], ind, root;
void rotate(int p) {
    int q = fa[p], y = fa[q], x = ch[q][1] == p;
    ch[q][x] = ch[p][x ^ 1];
    fa[ch[q][x]] = q;
    ch[p][x ^ 1] = q;
    fa[q] = p;
    fa[p] = y;
    if (y)
        if (ch[y][0] == q)
            ch[y][0] = p;
        else if (ch[y][1] == q)
            ch[y][1] = p;
}
void splay(int x) {
    for (int y; y = fa[x]; rotate(x))
        if (fa[y])
            rotate((ch[fa[y]][0] == y) == (ch[y][0] == x) ? y : x);
    root = x;
}
int search(int v) {
    int p = root;
    while (p && k[p] != v) p = ch[p][k[p] < v];
    if (p)
        splay(p);
    return p;
}
void insert(int v) {
    if (root == 0) {
        root = ++ind;
        k[root] = v;
    } else if (search(v) == 0) {
        int p = root;
        while (p && ch[p][k[p] < v]) p = ch[p][k[p] < v];
        ch[p][k[p] < v] = ++ind;
        fa[ind] = p;
        k[ind] = v;
        splay(ind);
    }
}
int prefix(int p) {
    p = search(p);
    if (!p)
        return 0;
    splay(p);
    int t = ch[p][0];
    while (t && ch[t][1]) t = ch[t][1];
    return t;
}
int suffix(int p) {
    p = search(p);
    if (!p)
        return 0;
    splay(p);
    int t = ch[p][1];
    while (t && ch[t][0]) t = ch[t][0];
    return t;
}
}  // namespace Splay

int main() {
    ios::sync_with_stdio(false);
    int n, a;
    long long ans = 0;
    cin >> n;
    Splay::insert(-INT_MAX / 2);
    Splay::insert(INT_MAX / 2);
    cin >> a;
    Splay::insert(a);
    ans += a;
    for (int i = 2; i <= n; i++) {
        cin >> a;
        if (Splay::search(a) == 0) {
            Splay::insert(a);
            // cout<<"now = "<<a<<"  prev="<<Splay::k[Splay::prefix(a)]<<"
            // suff="<<Splay::k[Splay::suffix(a)]<<endl;
            ans += min(Splay::k[Splay::suffix(a)] - a, a - Splay::k[Splay::prefix(a)]);
        } else {
            Splay::insert(a);
        }
    }
    cout << ans << endl;
}

10144. 「一本通 4.6 练习 1」宠物收养所

#include <bits/stdc++.h>
using namespace std;

const int SN = 2000005;

namespace Splay {
int k[SN], sz[SN], cnt[SN], fa[SN], ch[SN][2], ind, root;
void pushup(int p) { sz[p] = sz[ch[p][0]] + sz[ch[p][1]] + cnt[p]; }
void rotate(int p) {
    int q = fa[p], y = fa[q], x = ch[q][1] == p;
    ch[q][x] = ch[p][x ^ 1];
    fa[ch[q][x]] = q;
    ch[p][x ^ 1] = q;
    fa[q] = p;
    fa[p] = y;
    if (y)
        ch[y][ch[y][1] == q] = p;
    pushup(q);
    pushup(p);
}
void splay(int x) {
    for (int y; y = fa[x]; rotate(x))
        if (fa[y])
            rotate((ch[fa[y]][0] == y) == (ch[y][0] == x) ? y : x);
    root = x;
}
int search(int v) {
    int p = root;
    while (p && (k[p] - v)) p = ch[p][k[p] < v];
    return p;
}
void insert(int v) {
    if (root == 0) {
        root = ++ind;
        k[root] = v;
        sz[root] = cnt[root] = 1;
    } else if (search(v)) {
        int tmp = search(v);
        splay(tmp);
        sz[tmp]++;
        cnt[tmp]++;
    } else {
        int p = root;
        while (p && ch[p][k[p] < v]) p = ch[p][k[p] < v];
        ch[p][k[p] < v] = ++ind;
        fa[ind] = p;
        k[ind] = v;
        sz[ind] = cnt[ind] = 1;
        splay(ind);
    }
}
void remove(int p) {
    if (p == 0)
        return;
    splay(p);
    if (cnt[p] > 1) {
        cnt[p]--;
        sz[p]--;
        return;
    }
    int l = ch[p][0], r = ch[p][1];
    fa[l] = fa[r] = 0;
    ch[p][0] = ch[p][1] = 0;
    if (l == 0) {
        root = r;
        return;
    }
    if (r == 0) {
        root = l;
        return;
    }
    int t = l;
    while (t && ch[t][1]) t = ch[t][1];
    root = l;
    splay(t);
    ch[t][1] = r;
    fa[r] = t;
    pushup(t);
}
void remove_v(int v) { remove(search(v)); }
int rank(int p) {
    splay(p);
    return sz[ch[p][0]] + 1;
}
int rank_v(int v) { return rank(search(v)); }
int kth(int p, int k) {
    if (k <= sz[ch[p][0]])
        return kth(ch[p][0], k);
    if (k <= sz[ch[p][0]] + cnt[p])
        return p;
    else
        return kth(ch[p][1], k - sz[ch[p][0]] - cnt[p]);
}
int kth(int k0) { return kth(root, k0); }
int kth_v(int k0) { return k[kth(k0)]; }
int prefix(int p) {
    splay(p);
    int t = ch[p][0];
    while (t && ch[t][1]) t = ch[t][1];
    return t;
}
int prefix_v(int v) {
    insert(v);
    int r_ans = prefix(search(v));
    remove(search(v));
    return r_ans;
}
int suffix(int p) {
    splay(p);
    int t = ch[p][1];
    while (t && ch[t][0]) t = ch[t][0];
    return t;
}
int suffix_v(int v) {
    insert(v);
    int r_ans = suffix(search(v));
    remove(search(v));
    return r_ans;
}
}  // namespace Splay

int n, a, b, cnt;
long long ans;

int main() {
    // ios::sync_with_stdio(false);
    cin >> n;
    Splay::insert(INT_MAX / 2);
    Splay::insert(-INT_MAX / 2);
    for (int i = 1; i <= n; i++) {
        cin >> a >> b;
        if ((cnt >= 0 && a == 1) || (cnt <= 0 && a == 0)) {
            Splay::insert(b);
        } else {
            int p = Splay::prefix_v(b), pv = Splay::k[p];
            int s = Splay::suffix_v(b), sv = Splay::k[s];
            if (Splay::search(b)) {
                Splay::remove(b);
            } else if (b - pv <= sv - b) {
                ans += b - pv;
                Splay::remove(p);
            } else {
                ans += sv - b;
                Splay::remove(s);
            }
        }
        if (a)
            ++cnt;
        else
            --cnt;
    }
    cout << ans % 1000000 << endl;
}

10145. 「一本通 4.6 练习 2」郁闷的出纳员

#include <bits/stdc++.h>
using namespace std;

const int SN = 2000005;

namespace Splay {
int k[SN], sz[SN], cnt[SN], fa[SN], ch[SN][2], ind, root;
void pushup(int p) { sz[p] = sz[ch[p][0]] + sz[ch[p][1]] + cnt[p]; }
void rotate(int p) {
    int q = fa[p], y = fa[q], x = ch[q][1] == p;
    ch[q][x] = ch[p][x ^ 1];
    fa[ch[q][x]] = q;
    ch[p][x ^ 1] = q;
    fa[q] = p;
    fa[p] = y;
    if (y)
        ch[y][ch[y][1] == q] = p;
    pushup(q);
    pushup(p);
}
void splay(int x) {
    for (int y; y = fa[x]; rotate(x))
        if (fa[y])
            rotate((ch[fa[y]][0] == y) == (ch[y][0] == x) ? y : x);
    root = x;
}
int search(int v) {
    int p = root;
    while (p && (k[p] - v)) p = ch[p][k[p] < v];
    return p;
}
void insert(int v) {
    if (root == 0) {
        root = ++ind;
        k[root] = v;
        sz[root] = cnt[root] = 1;
    } else if (search(v)) {
        int tmp = search(v);
        splay(tmp);
        sz[tmp]++;
        cnt[tmp]++;
    } else {
        int p = root;
        while (p && ch[p][k[p] < v]) p = ch[p][k[p] < v];
        ch[p][k[p] < v] = ++ind;
        fa[ind] = p;
        k[ind] = v;
        sz[ind] = cnt[ind] = 1;
        splay(ind);
    }
}
void remove(int p) {
    if (p == 0)
        return;
    splay(p);
    if (cnt[p] > 1) {
        cnt[p]--;
        sz[p]--;
        return;
    }
    int l = ch[p][0], r = ch[p][1];
    fa[l] = fa[r] = 0;
    ch[p][0] = ch[p][1] = 0;
    if (l == 0) {
        root = r;
        return;
    }
    if (r == 0) {
        root = l;
        return;
    }
    int t = l;
    while (t && ch[t][1]) t = ch[t][1];
    root = l;
    splay(t);
    ch[t][1] = r;
    fa[r] = t;
    pushup(t);
}
void remove_v(int v) { remove(search(v)); }
int rank(int p) {
    splay(p);
    return sz[ch[p][0]] + 1;
}
int rank_v(int v) { return rank(search(v)); }
int kth(int p, int k) {
    if (k <= sz[ch[p][0]])
        return kth(ch[p][0], k);
    if (k <= sz[ch[p][0]] + cnt[p])
        return p;
    else
        return kth(ch[p][1], k - sz[ch[p][0]] - cnt[p]);
}
int kth(int k0) { return kth(root, k0); }
int kth_v(int k0) { return k[kth(k0)]; }
int prefix(int p) {
    splay(p);
    int t = ch[p][0];
    while (t && ch[t][1]) t = ch[t][1];
    return t;
}
int prefix_v(int v) {
    insert(v);
    int r_ans = prefix(search(v));
    remove(search(v));
    return r_ans;
}
int suffix(int p) {
    splay(p);
    int t = ch[p][1];
    while (t && ch[t][0]) t = ch[t][0];
    return t;
}
int suffix_v(int v) {
    insert(v);
    int r_ans = suffix(search(v));
    remove(search(v));
    return r_ans;
}
int getmax() {
    int p = root;
    while (p && ch[p][1]) p = ch[p][1];
    return p;
}
}  // namespace Splay

int n, lim, offset, t, cnt;
char op;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> lim;
    for (int i = 1; i <= n; i++) {
        cin >> op >> t;
        if (op == 'I')
            if (t >= lim)
                Splay::insert(-(t - offset));
        if (op == 'A')
            offset += t;
        if (op == 'S')
            offset -= t;
        if (op == 'F') {
            if (t <= Splay::sz[Splay::root])
                cout << -Splay::kth_v(t) + offset << endl;
            else
                cout << "-1" << endl;
        }
        while (Splay::sz[Splay::root] && -Splay::k[Splay::getmax()] + offset < lim)
            Splay::remove(Splay::getmax()), ++cnt;
    }
    cout << cnt << endl;
}