权值树状数组（ - 帖子

权值线段树貌似是在值域建立线段树，我不想敲线段树（才不是想不出操作 4 怎么写），所以就维护了个树状数组。

前三个操作好说，第四个操作套个二分就完事了。不过首先要离散化一下，所以这玩意只能离线。

前三个操作单次，第四个操作复杂度。所以这个算法的时间复杂度理论上界为，但是由于 Star 并没有构造这样的数据，所以能成功卡过。而且加上快读跑得比线段树还快。

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 10;

int val[MAXN];

int c[MAXN];
int n;

// BIT operations

inline void modify(int x, int v)
{
    while (x <= n) {
        c[x] += v;
        x += x & -x;
    }
}

inline int query(int x)
{
    int ans = 0;
    while (x) {
        ans += c[x];
        x -= x & -x;
    }
    return ans;
}

// Other operations

void insert(int x)
{
    modify(x, 1);
}

void remove(int x)
{
    modify(x, -1);
}

int qrank(int x)
{
    return query(x - 1) + 1;
}

int qid(int x)
{
    int l = 0, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        int s = query(mid);
        if (s < x) {
            l = mid + 1;
        }
        else {
            r = mid;
        }
    }
    return l;
}

struct option_type {
    int opt, x;
    int index;
} op[MAXN];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> op[i].opt >> op[i].x;
        op[i].index = i;
    }

    sort(op + 1, op + n + 1, [](const option_type &a, const option_type &b)
    -> const bool {
        return (a.opt == 4 || b.opt == 4) ? a.opt < b.opt : a.x < b.x;
    });

    for (int i = 1, id = 0; i <= n && op[i].opt != 4; i++) {
        if (op[i].x != val[op[i - 1].x]) id++;
        val[id] = op[i].x;
        op[i].x = id;
    }

    sort(op + 1, op + n + 1, [](const option_type &a, const option_type &b)
    -> const bool {
        return a.index < b.index;
    });

    for (int i = 1; i <= n; i++) {
        switch (op[i].opt) {
            case 1:
                insert(op[i].x);
                break;
            case 2:
                remove(op[i].x);
                break;
            case 3:
                cout << qrank(op[i].x) << '\n';
                break;
            case 4:
                cout << val[qid(op[i].x)] << '\n';
                break;
            default:
                cout << "1145141919810\n";
                return 0;
        }
    }

    return 0;
}