COCI 2021 - Index

#ifdef LOCAL
#include <iostream>
#include <fstream>
#include <iomanip>
#include <random>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#else
#include <bits/stdc++.h>
#define cerr if (false) cerr
#define endl '\n'
#endif

#define fi first
#define se second

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))

#define bit(mask, i) (((mask) >> (i)) & 1)
#define popcount(x) __builtin_popcount(x)

#define YES cout << "YES" << endl
#define NO cout << "NO" << endl

using namespace std;

template <typename T>
bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
template <typename T>
bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }

using ll = long long;
using pii = pair<int, int>;

const int NMAX = 2e5+5;
const int NIL  = -1;

struct PerSegTree {
   struct Node {
      int cnt, lchild, rchild;
   };

   int n;
   vector<Node> v;
   vector<int> root;

   PerSegTree(int _n): n(_n), root({ build(1, n) }) { }

   int build(int l, int r) {
      if (l >= r) {
         Node node = { 0, NIL, NIL };
         v.push_back(node);
         return sz(v) - 1;
      }

      int mid = (l + r) >> 1;

      Node node = { 0, build(l, mid), build(mid + 1, r) };

      v.push_back(node);
      return sz(v) - 1;
   }

   void update_val(int k, int pos, int val) {
      root[k] = update_val(root[k], 1, n, pos, val);
   }

   int update_val(int u, int l, int r, int pos, int val) {
      if (pos < l || r < pos) return u;

      if (l >= r) {
         Node node = { val, NIL, NIL };
         v.push_back(node);
         return sz(v) - 1;
      }

      int mid = (l + r) >> 1;

      Node node = { 0,
         update_val(v[u].lchild, l, mid, pos, val),
         update_val(v[u].rchild, mid + 1, r, pos, val)
      };

      node.cnt = v[node.lchild].cnt + v[node.rchild].cnt;

      v.push_back(node);
      return sz(v) - 1;
   }

   int query_cnt_greater(int k, int l, int r) {
      return r - l + 1 - query_cnt(root[k - 1], 1, n, l, r);
   }

   int query_cnt(int u, int l, int r, int ll, int rr) {
      if (ll <= l && r <= rr)
         return v[u].cnt;

      int mid = (l + r) >> 1;
      int cnt = 0;

      if (ll <= mid) cnt = query_cnt(v[u].lchild, l, mid, ll, rr);
      if (mid < rr) cnt += query_cnt(v[u].rchild, mid + 1, r, ll, rr);

      return cnt;
   }

   void update_copy(int k) {
      v.push_back(v[root[k]]);
      root.push_back(sz(v) - 1);
   }
};

int n, m, max_val;
vector<int> a[NMAX];

void read() {
   cin >> n >> m;
   for (int i = 1, x; i <= n; i++) {
      cin >> x;
      max_val = max(max_val, x);
      a[x].push_back(i);
   }
}

int query(PerSegTree &tree, int ll, int rr) {
   int l = 1, r = max_val;

   while (l <= r) {
      int mid = (l + r) >> 1;
      if (tree.query_cnt_greater(mid, ll, rr) >= mid) l = mid + 1;
      else r = mid - 1;
   }

   return r;
}

void solve() {
   PerSegTree tree(n);


   for (int val = 1; val <= max_val; val++) {
      tree.update_copy(val - 1);
      for (auto &pos : a[val])
         tree.update_val(val, pos, 1);
   }

   while (m--) {
      int l, r;
      cin >> l >> r;
      cout << query(tree, l, r) << endl;
   }
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   read();
   solve();

   return 0;
}