[Codeforces] 840 - D. Destiny

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 840 - D. Destiny
Source            : Codeforces
Category          : Data Structure
Algorithm         : MO's Algorithm, Hilbert Order
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 310000;  
  
struct mo  
{  
      int l, r, k, id;  
      int64_t ord;  
      mo(int l = 0, int r = 0, int k = 0, int id = 0, int64_t ord = 0)  
            : l(l)  
            , r(r)  
            , k(k)  
            , id(id)  
            , ord(ord)  
            {}  
  
      friend bool operator < (mo p, mo q)  
      {  
            return p.ord < q.ord;  
      }  
} queries[maxn];  
  
inline int64_t hilbertOrder(int x, int y, int pow, int rotate)  
{  
      if (pow == 0)  
      {  
            return 0;  
      }  
    int hpow = 1 << (pow-1);  
    int seg = (x < hpow) ? (  
        (y < hpow) ? 0 : 3  
    ) : (  
        (y < hpow) ? 1 : 2  
    );  
    seg = (seg + rotate) & 3;  
    const int rotateDelta[4] = {3, 0, 0, 1};  
    int nx = x & (x ^ hpow), ny = y & (y ^ hpow);  
    int nrot = (rotate + rotateDelta[seg]) & 3;  
    int64_t subSquareSize = int64_t(1) << (2*pow - 2);  
    int64_t ans = seg * subSquareSize;  
    int64_t add = hilbertOrder(nx, ny, pow-1, nrot);  
    ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);  
    return ans;  
}  
  
int arr[maxn], freq[maxn], ans[maxn];  
int l = 1, r = 0;  
  
void add(int pos)  
{  
      int x = arr[pos];  
      freq[x]++;  
}  
  
void remov(int pos)  
{  
      int x = arr[pos];  
      freq[x]--;  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n, q;  
      cin >> n >> q;  
      for (int i = 1; i <= n; i++) cin >> arr[i];  
      for (int i = 1; i <= q; i++)  
      {  
            int l, r, k;  
            cin >> l >> r >> k;  
            int64_t ord = hilbertOrder(l, r, 21, 0);  
            queries[i] = mo(l, r, k, i, ord);  
      }  
      sort(queries+1, queries+q+1);  
      mt19937 rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());  
      for (int i = 1; i <= q; i++)  
      {  
            int L = queries[i].l;  
            int R = queries[i].r;  
            int K = queries[i].k;  
            while (l > L) add(--l);  
            while (r < R) add(++r);  
            while (l < L) remov(l++);  
            while (r > R) remov(r--);  
            int req = (R-L+1) / K;  
            int op = 80;  
            int mini = 1e9;  
            while (op--)  
            {  
                  int idx = uniform_int_distribution <int> (L, R)(rng);  
                  if (idx < L || idx > R) continue;  
                  if (freq[ arr[idx] ] > req) mini = min(mini, arr[idx]);  
            }  
            if (mini == 1e9) mini = -1;  
            ans[ queries[i].id ] = mini;  
      }  
      for (int i = 1; i <= q; i++) cout << ans[i] << '\n';  
}