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

Задача C. Поиск медианы

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

3 секунды

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

512 мегабайт

Дан массив чисел $a$ длинны $n$ и $q$ запросов. Каждый из запросов описывается числами $l$ и $r$. Для каждого из запросов нужно найти, какой будет медиана в массиве, если удалить числа из массива от $l$ до $r$.

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

В первой строке входных данных подаются 2 числа $n, q$ $(1 <= n, q <= 10^6)$ — количество чисел в массиве и количество запросов. Во второй строке входных данных подаются $n$ целых чисел $a_i$ $(1 <= a_i <= 10^9)$ — $i$-й элемент массива $a$. В последующих $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;
}