4-й этап Республиканской олимпиады по информатике 2019, 9 класс, Актобе

Есеп C. Медиана

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

3 seconds

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

512 megabytes

Ұзындығы $n$ болатын $a$ массивы пен $q$ сұратулар бар. Әр сұрату $l$ және $r$ сандарымен сипатталады. Әр сұрату үшін, $l$-ден $r$-ға дейінгі массив элементтерін алып тастағандағы калған массивтың медианасын табу керек.

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

Бірінші жолда екі сан $n, q$ $(1 <= n, q <= 10^6)$ — массивтың ұзындығы мен сұратулар саны беріледі. Екінші жолда $n$ бүтін сан $a_i$ $(1 <= a_i <= 10^9)$ — $a$ массивының $i$-шы саны беріледі. Келесі $q$ жолда екі саннан $l, r$ $(1 <= l <= r <= n)$ — алынатын кесіндінің шеттері беріледі. Қалған массивте ең болмаса бір сан қалатынына кепілдік беріледі.

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

Әр сұрату үшін, бөлек жолдарда, қалған массивтың медианасын шығарыңыз.

Система оценки

Есеп алты бөлімнен тұрады:

1. $1 <= n <= 1000, 1 <= q <= 1000, 1 <= a_i <= 10^9$. $8$ ұпайға бағаланады.
2. $1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= a_{i + 1} <= 10^9$. $9$ ұпайға бағаланады.
3. $1 <= n <= 100000, 1 <= q <= 10000, 1 <= a_i <= 10^9$. $19$ ұпайға бағаланады.
4. $1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= 100$. $15$ ұпайға бағаланады.
5. $1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= 10^9$. $31$ ұпайға бағаланады.
6. $1 <= n <= 500000, 1 <= q <= 1000000, 1 <= a_i <= 10^9$. $18$ ұпайға бағаланады.

Пример:

Вход

5 5
1 2 1 4 9
2 4
1 1
4 5
3 4
1 3

Ответ

1
2
1
2
4

Замечание

Ұзындығы $n$ болатын массивтың медианасы деп, массивтың сорттаудан кейінгі $\frac{n+1}{2}$ орнында тұратын санды атайды. Бірінші мысалда, бірінші сұратудан кейін, $[2, 1, 4]$ тізбегі жоғалып $[1, 9]$ массивы қалады. Қалған массивтың ұзындығы $2$ болғандықтан, медиананың орны $\frac{3}{2} = 1$ тең. Екінші сұратудан кейін, $[1]$ тізбегі жоғалып $[2, 1, 4, 9]$ массивы қалады. Қалған массивтың ұзындығы $4$ болғандықтан, медиананың орны $\frac{5}{2} = 2$-тең. Қалған массивтың сортталған түріндегі екінші элементі $2$-тең. Үшінщі сұратудан кейін, $[4, 9]$ тізбегі жоғалып $[1, 2, 1]$ массивы қалады. Қалған массивтың ұзындығы $3$ болғандықтан, медиананың орны $\frac{4}{2} = 2$-тең. Қалған массивтың сортталған түріндегі екінші элементі $1$-тең. ( Nurdaulet Akhanov )

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

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

#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 pb push_back
#define pc __builtin_popcount
#define pcll __builtin_popcountll
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
using namespace std;
int n, q, a[1000005];
vector<int> b;
struct node {
  node *l, *r;
  int sum;
  node(int new_sum = 0) {
    l = r = nullptr;
    sum = new_sum;
  }
} * ver[1000005];
void build(node *v, int l, int r) {
  if (l == r) {
    v->sum = 0;
    return;
  }
  int tm = (l + r) / 2;
  v->l = new node();
  v->r = new node();
  build(v->l, l, tm);
  build(v->r, tm + 1, r);
  v->sum = (v->l)->sum + (v->r)->sum;
}
void upd(node *v, node *pv, int l, int r, int pos, int val) {
  if (l == r) {
    v->sum = pv->sum + val;
    return;
  }
  int tm = (l + r) / 2;
  if (pos <= tm) {
    v->r = pv->r;
    v->l = new node();
    upd(v->l, pv->l, l, tm, pos, val);
  } else {
    v->l = pv->l;
    v->r = new node();
    upd(v->r, pv->r, tm + 1, r, pos, val);
  }
  v->sum = (v->l)->sum + (v->r)->sum;
}
int get(node *vl, node *vr, node *vn, int val, int l = 1, int r = n) {
  if (l == r) return l;
  int tm = (l + r) / 2;
  int cur = (vn->l)->sum - (vr->l)->sum + (vl->l)->sum;
  if (val <= cur)
    return get(vl->l, vr->l, vn->l, val, l, tm);
  else
    return get(vl->r, vr->r, vn->r, val - cur, tm + 1, r);
}
int main() {
  speed;
  oprecision;
  // code
  cin >> n >> q;
  forn(n) cin >> a[i], b.pb(a[i]), ver[i] = new node();
  sort(b.begin(), b.end());
  b.erase(unique(b.begin(), b.end()), b.end());
  forn(n) a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
  ver[0] = new node();
  build(ver[0], 1, n);
  forn(n) upd(ver[i], ver[i - 1], 1, n, a[i], 1);
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << b[get(ver[l - 1], ver[r], ver[n], (n - (r - l + 1) + 1) / 2) - 1]
         << "\n";
  }
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}