FOCUS - Chuyên gia ruồi
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 200005;
const int add = 1;
const int del = -1;
const int cnt = 2;
struct e {
int type, a, b, k;
};
using namespace std;
e event[N];
ii b[N];
int mirror[N], bit[N];
int n, m, d;
int BS(int key) {
int l = 0, r = d, k = 0, m;
while (l <= r) {
m = (l + r) >> 1;
if (mirror[m] <= key) {
k = m; l = m + 1;
}
else
r = m - 1;
}
return k;
}
void Upd(int i, int v) {
while (i <= d) {
bit[i] += v;
i += i & (-i);
}
}
int Get(int i) {
int s = 0;
while (i) {
s += bit[i];
i -= i & (-i);
}
return s;
}
void Enter() {
scanf("%d\n", &n);
int i; char c;
for(i=1; i<=n; i++) {
scanf("%c ", &c);
if (c == '+') {
event[i].type = add;
scanf("%d\n", &event[i].a);
b[++m] = ii(event[i].a, i);
}
if (c == '-') {
event[i].type = del;
scanf("%d\n", &event[i].a);
b[++m] = ii(event[i].a, i);
}
if (c == '?') {
event[i].type = cnt;
scanf("%d %d %d\n", &event[i].k, &event[i].a, &event[i].b);
}
}
sort(b+1, b+1+m);
for(i=1; i<=m; i++) {
if (b[i].X != b[i-1].X) d++;
event[b[i].Y].a = d;
mirror[d] = b[i].X;
}
}
void Answer() {
int i, L, R, mid, VL, res;
for(i=1; i<=n; i++) {
if (event[i].type != cnt)
Upd(event[i].a, event[i].type);
else {
L = BS(event[i].a - 1);
R = BS(event[i].b);
VL = Get(L);
if (R == 0 || Get(R) - VL < event[i].k) {
printf("0\n"); continue;
}
while (L <= R) {
mid = (L + R) >> 1;
if (Get(mid) - VL >= event[i].k) {
res = mid;
R = mid - 1;
}
else
L = mid + 1;
}
printf("%d\n", mirror[res]);
}
}
}
int main()
{
Enter();
Answer();
return 0;
}