AcWing 253. 树状数组 50行解决~
原题链接
中等
作者:
夜林
,
2021-06-23 14:44:14
,
所有人可见
,
阅读 742
树状数组
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, tot, sz;
int opt[N], val[N], num[N], c[N];
int pos(int x) {
return lower_bound(num + 1, num + 1 + sz, x) - num;
}
void add(int x, int k) {
for (x; x <= sz; x += x & -x) c[x] += k;
}
int query(int x) {
int tmp = 0;
for (x; x; x -= x & -x) tmp += c[x];
return tmp;
}
int kth(int x) {
int rs = 0;
for (int i = 17; i >= 0; --i) {
rs += (1 << i);
if (rs > sz || c[rs] >= x)
rs -= (1 << i);
else
x -= c[rs];
}
return num[rs + 1];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &opt[i], &val[i]);
if (opt[i] != 4) num[++tot] = val[i];
}
sort(num + 1, num + 1 + tot);
sz = unique(num + 1, num + 1 + tot) - num - 1;
for (int i = 1; i <= n; ++i) {
int x = val[i];
if (opt[i] == 1) add(pos(x), 1);
else if (opt[i] == 2) add(pos(x), -1);
else if (opt[i] == 3) printf("%d\n", query(pos(x) - 1) + 1);
else if (opt[i] == 4) printf("%d\n", kth(x));
else if (opt[i] == 5) printf("%d\n", kth(query(pos(x) - 1)));
else printf("%d\n", kth(query(pos(x)) + 1));
}
return 0;
}