Республиканская олимпиада по информатике 2009 год

Есеп B. Сиқыр

Ограничение по времени:

2 секунд

Ограничение по памяти:

256 мегабайт

Баханың шыбындармен ойлап таплап сиқыры есіңізде ме? Жома онымен жарысуды ұйғарып, өз сиқырын ойлап тапты. Жомада жәшік бар. Ол онда шыбынды кіргізе немесе шығара алады. Сонымен қатар, ол жақсы жаттықтырушы ретінде әр шыбынның туғаннан бастап өмір жасын әр минутына дейін біледі. Сиқыр сипаттамасы: уақыттың әр сәтінде ол жәшіктегі жасы $A$-дан $B$-ға (шеткі мәндерді қоса) дейнгі шыбындардың ішінен жасының үлкендігіне қарай $K$-ші болатын шыбынның жасын айтып бере алады. Сіз де осындай сиқыр жасап көріңіз!

Формат входного файла

Енгізу файлының бірінші жолында $N$ — оқиғалардың жалпы саны ($1 \le N \le 2 \cdot 10^5$). Әрі қарай N жол берілген, әрқайсысы оқиғалардың бірін сипаттайды:

• $+ X$ — жәшікке жасы $X$ болатын шыбынды кіргізді;
• $- X$ — жәшіктен жасы $X$ болатын шыбынды шығарды;
• $? K A B$ — сиқыршыдан жәшіктегі жасы $A$-дан $B$-ға дейнгі шыбындардың ішінен жасының үлкендігіне қарай $K$-ші болатын шыбынның жасын сұрады ($1 \le K \le 10^5$, $A \le B$).

Шыбынның жасы ($X$, $A$, $B$) — $1$-ден $10^9$-ге дейінгі бүтін сан.

Формат выходного файла

Шығыс файлда саны — енгізу файлдағы жас шамасы туралы сұраныстардың санындай болатын жолдар болуы тиіс. Әрбір осындай сұраныс үшін сәйкесінше санды — сұранысқа жауапты құрайтын жолды шығару керек. Егер жәшіктегі жасы $A$-дан $B$-ға дейнгі шыбындардың саны $K$-дан кіші болса, онда $0$-ді шығару керек.

Пример:

Вход

8
+ 2
+ 3
+ 2
? 2 2 3
- 2
? 2 2 3
- 2
? 2 2 3

Ответ

2
3
0

Комментарий/решение

кодты корсету/жасыру

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define ll long long
#define ld long double
#define ss string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) \
  for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++))
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pb(x) push_back(x)
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define mp(x, y) make_pair(x, y)
#define F first
#define S second
using namespace std;
int q;
unordered_map<int, int> t;
void upd(int x, int y) {
  for (; x <= 1000000000; x += (x & -x)) t[x] += y;
}
int get(int x) {
  int y = 0;
  for (; x > 0; x -= (x & -x)) y += t[x];
  return y;
}
int find(int s) {
  int k = 0;
  for (int l = 29; l >= 0; l--) {
    if (k + (1 << l) <= 1000000000 && t[k + (1 << l)] < s) {
      k += (1 << l);
      s -= t[k];
    }
  }
  return k + 1;
}
int main() {
  speed;
  oprecision;
  // code
  t.reserve(1 << 16);
  t.max_load_factor(0.2);
  cin >> q;
  while (q--) {
    char type;
    int a, b, c;
    cin >> type >> a;
    if (type == '+') {
      upd(a, 1);
    }
    if (type == '-') {
      upd(a, -1);
    }
    if (type == '?') {
      cin >> b >> c;
      int d = find(get(b - 1) + a);
      cout << (d > c ? 0 : d) << "\n";
    }
  }
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}