Kyselyt

#include <bits/stdc++.h>
using namespace std;
#define N (1 << 18)
typedef vector<int> VI;

vector<int> cnts2[2 * N + 10];
vector<pair<int, int>> cnts3[2 * N + 10];
int lz[2 * N + 10];
int cms[2 * N + 10];

void put(int i, int x) {
  i += N;
  i /= 2;
  while (i >= 1) {
    i /= 2;
  }
}
void init(int n, VI &x) {
  // for (int i = 1; i <= n; i++) {
  //   put(i, x[i]);
  // }
  for (int i = N; i >= 1; i--) {
    if (i * 2 > N) {
      if (i * 2 - N <= n) {
        cnts2[i].push_back(x[i * 2 - N]);
        lz[i * 2] = 1;
        lz[i]++;
      }
    } else {
      for (auto u : cnts2[i * 2]) {
        cnts2[i].push_back(u);
      }
      lz[i] += lz[i * 2];
    }
    if (i * 2 + 1 > N) {
      if (i * 2 + 1 - N <= n) {
        cnts2[i].push_back(x[i * 2 + 1 - N]);
        lz[i]++;
        lz[i * 2 + 1] = 1;
      }
    } else {
      for (auto u : cnts2[i * 2 + 1]) {
        cnts2[i].push_back(u);
      }
      lz[i] += lz[i * 2 + 1];
    }
    sort(cnts2[i].begin(), cnts2[i].end());
    int b1 = 0;
    int b2 = 0;
    int cnt = 0;
    int pv = 0;
    for (auto u : cnts2[i]) {
      if (u != pv) {
        if (cnt) {
          cnts3[i].push_back({pv, cnt});
          if (cnt > b1) {
            b1 = cnt;
            b2 = pv;
          }
        }
        cnt = 0;
        pv = u;
      }
      cnt++;
    }
    if (cnt) {
      cnts3[i].push_back({pv, cnt});
    }
    if (cnt > b1) {
      b1 = cnt;
      b2 = pv;
    }
    if (b1 > lz[i] / 2)
      cms[i] = b2;
  }
  for (int i = N + 1; i <= N + n; i++)
    cms[i] = x[i - N];
}

int hm(int i, int x) {
  auto it = lower_bound(cnts3[i].begin(), cnts3[i].end(), make_pair(x, 0));
  if (it == cnts3[i].end() || it->first != x)
    return 0;
  return it->second;
}

int cq(int a, int b, int x, VI &xs) {
  int ret = 0;
  a += N;
  b += N;
  int cr = 0;
  while (a <= b) {
    if (a % 2 == 1) {
      if (a > N)
        ret += xs[a - N] == x;
      else
        ret += hm(a, x);
 //       ret += cnts[a][x];
      cr += lz[a];
      a++;
    }
    if (b % 2 == 0) {
      if (b > N)
        ret += xs[b - N] == x;
      else
        ret += hm(b, x);
        // ret += cnts[b][x];
      cr += lz[b];
      b--;
    }
    a /= 2;
    b /= 2;
  }
  return ret;
}

int sq(int A, int B, VI &x) {
  int a = A + N;
  int b = B + N;
  vector<int> mc;
  while (a <= b) {
    if (a % 2 == 1) {
      if (cms[a] && find(mc.begin(), mc.end(), cms[a]) == mc.end())
        mc.push_back(cms[a]);
      a++;
    }
    if (b % 2 == 0) {
      if (cms[b] && find(mc.begin(), mc.end(), cms[b]) == mc.end())
        mc.push_back(cms[b]);
      b--;
    }
    a /= 2;
    b /= 2;
  }
  int yhyy = 0;
  for (auto u : mc) {
    int c = cq(A, B, u, x);
    yhyy += c;
    if (c > (B - A + 1) / 2)
      return u;
  }
  return -1;
}

int query(int a, int b, VI &x) { return sq(a, b, x); }

void solve(int n, int q, VI &x, VI &a, VI &b) {
  init(n, x);
  for (int i = 0; i < q; i++) {
    cout << query(a[i], b[i], x) << "\n";
  }
}

void test() {
  int n = 2e5;
  int q = 2e5;
  VI a(q), b(q);
  VI x(n + 1);
  for (int i = 1; i <= n; i++)
    x[i] = rand() % 10000;
  for (int i = 0; i < q; i++) {
    a[i] = rand() % 1000;
    b[i] = (a[i] + rand()) % n;
  }

  solve(n, q, x, a, b);
  exit(0);
}

int main() {
  // test();
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  VI x(n + 1);
  for (int i = 1; i <= n; i++)
    cin >> x[i];
  VI a(q), b(q);
  for (int i = 0; i < q; i++) {
    cin >> a[i] >> b[i];
  }
  solve(n, q, x, a, b);
}

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

Test 4

Group: 2, 3, 4

Verdict: ACCEPTED

Test 5

Group: 2, 3, 4

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

Test 7

Group: 3, 4

Verdict: ACCEPTED

Test 8

Group: 4

Verdict: ACCEPTED

Test 9

Group: 4

Verdict: ACCEPTED

Test 10

Group: 4

Verdict: ACCEPTED

Test 11

Group: 3, 4

Verdict: ACCEPTED

Test 12

Group: 4

Verdict: ACCEPTED

Test 13

Group: 3, 4

Verdict: ACCEPTED

Test 14

Group: 4

Verdict: ACCEPTED

Test 15

Group: 4

Verdict: ACCEPTED

Test 16

Group: 4

Verdict: ACCEPTED