FOCUS - Chuyên gia ruồi
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <iomanip>
#include <fstream>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <functional>
#include <ctime>
#include <cstdio>
#include <cstdarg>
using namespace std;
#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define Fill(a,b) memset( (a), (b), sizeof(a))
#define pb push_back
#define MP make_pair
#define fi first
#define se second
typedef pair<int,int> PII;
typedef pair<PII,PII> PP;
const int MAXN = 200020;
char buf[1000];
PP command[MAXN];
int dx[MAXN], nd;
int sum[MAXN * 4];
void add(int n, int l, int r, int pos, int v) {
sum[n] += v;
if(l == r) return;
int m = (l+r) / 2;
if(pos <= m) add( 2*n, l, m, pos, v);
else add( 2*n+1, m+1, r, pos, v);
}
void find(int n, int l, int r, int a, int b, int &k, int &pos) {
if(k == 0) return;
if(a <= l && r <= b) {
if(k > sum[n]) {
k -= sum[n];
return;
}
}
if(l == r) {
k = 0;
pos = l;
return;
}
int m = (l+r) / 2;
if(a <= m) find( 2*n, l, m, a, b, k, pos);
if(m < b) find( 2*n+1, m+1, r, a, b, k, pos);
}
int main() {
int m;
scanf("%d", &m);
gets(buf);
Rep(kk,m) {
int x, a, b;
gets(buf);
if(buf[0] == '+') {
sscanf( buf + 1, "%d", &x);
command[kk] = MP(MP(1,x),MP(0,0));
dx[nd++] = x;
}
else if(buf[0] == '-') {
sscanf( buf + 1, "%d", &x);
command[kk] = MP(MP(2,x),MP(0,0));
dx[nd++] = x;
}
else {
sscanf( buf + 1, "%d%d%d", &x, &a, &b);
command[kk] = MP(MP(3,x), MP(a,b));
}
}
sort( dx, dx + nd);
nd = unique( dx, dx + nd) - dx;
Rep(k,m) {
if(command[k].fi.fi == 1) {
int pos = lower_bound( dx, dx + nd, command[k].fi.se) - dx;
add( 1, 0, nd - 1, pos, 1);
}
else if(command[k].fi.fi == 2) {
int pos = lower_bound( dx, dx + nd, command[k].fi.se) - dx;
add( 1, 0, nd - 1, pos, -1);
}
else {
int a, b;
int kk = command[k].fi.se;
a = lower_bound( dx, dx + nd, command[k].se.fi) - dx;
b = upper_bound( dx, dx + nd, command[k].se.se) - dx;
--b;
if(a <= b) {
int pos = -1;
find( 1, 0, nd - 1, a, b, kk, pos);
if(pos == -1) printf("0\n");
else printf("%d\n", dx[pos]);
}
else printf("0\n");
}
}
return 0;
}