fork download
copy 
  1. #pragma GCC optimize("O3,unroll-loops")
  2.  
  3. #include <iostream>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int limN = 200005;
  9. const int BLOCK = 450;
  10. const int MAXB = limN / BLOCK + 5;
  11.  
  12. int n, q;
  13. int a[limN];
  14. int ind[limN];
  15. int mx[MAXB][MAXB];
  16. int vis[limN];
  17.  
  18. int head[limN];
  19. int sz[limN];
  20. int cur[limN];
  21. int position[limN];
  22. int cnt[limN];
  23.  
  24. inline void checkl(int i, int r, int id, int &ans) {
  25.     int v = a[i];
  26.     if (vis[v] == id) return;
  27.     vis[v] = id;
  28.  
  29.     if (sz[v] <= ans) return;
  30.  
  31.     int h = head[v];
  32.     int it = ind[i];
  33.     while (it + ans < sz[v] && position[h + it + ans] <= r) ++ans;
  34. }
  35.  
  36. inline void checkr(int i, int l, int id, int &ans) {
  37.     int v = a[i];
  38.     if (vis[v] == id) return;
  39.     vis[v] = id;
  40.  
  41.     if (sz[v] <= ans) return;
  42.  
  43.     int h = head[v];
  44.     int it = ind[i];
  45.     while (it - ans >= 0 && position[h + it - ans] >= l) ++ans;
  46. }
  47.  
  48. int query(int l, int r, int id) {
  49.     int bl = (l - 1) / BLOCK;
  50.     int br = (r - 1) / BLOCK;
  51.  
  52.     if (br - bl <= 1) {
  53.         int ans = 0;
  54.         for (int i = r; i >= l; --i)
  55.             checkr(i, l, id, ans);
  56.         return ans;
  57.     }
  58.  
  59.     int ans = mx[bl + 1][br - 1];
  60.  
  61.     for (int i = l; i <= (bl + 1) * BLOCK; ++i)
  62.         checkl(i, r, id, ans);
  63.  
  64.     for (int i = r; i >= br * BLOCK + 1; --i)
  65.         checkr(i, l, id, ans);
  66.  
  67.     return ans;
  68. }
  69.  
  70. int main() {
  71.     ios_base::sync_with_stdio(false);
  72.     cin.tie(NULL);
  73.  
  74.     cin >> n >> q;
  75.     for (int i = 1; i <= n; ++i) {
  76.         cin >> a[i];
  77.         ++sz[a[i]];
  78.     }
  79.  
  80.     head[1] = 0;
  81.     for (int i = 2; i <= 200000; ++i)
  82.         head[i] = head[i - 1] + sz[i - 1];
  83.  
  84.     for (int i = 1; i <= 200000; ++i)
  85.         cur[i] = head[i];
  86.  
  87.     for (int i = 1; i <= n; ++i) {
  88.         int v = a[i];
  89.         ind[i] = cur[v] - head[v];
  90.         position[cur[v]++] = i;
  91.     }
  92.  
  93.     int numblock = (n + BLOCK - 1) / BLOCK;
  94.     for (int i = 0; i < numblock; ++i) {
  95.         int cur = 0;
  96.         for (int j = i; j < numblock; ++j) {
  97.             for (int k = j * BLOCK + 1; k <= min(n, (j + 1) * BLOCK); ++k) {
  98.                 int v = a[k];
  99.                 ++cnt[v];
  100.                 if (cnt[v] > cur) cur = cnt[v];
  101.             }
  102.             mx[i][j] = cur;
  103.         }
  104.         for (int j = i * BLOCK + 1; j <= n; ++j)
  105.             --cnt[a[j]];
  106.     }
  107.  
  108.     long long lastans = 0;
  109.     for (int id = 1; id <= q; ++id) {
  110.         long long x, y;
  111.         cin >> x >> y;
  112.  
  113.         long long l = (x + lastans) % n + 1;
  114.         long long r = (y + lastans) % n + 1;
  115.  
  116.         if (l > r) swap(l, r);
  117.  
  118.         lastans = query(l, r, id);
  119.         cout << lastans << '\n';
  120.     }
  121.  
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0.01s 6392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vj8O4h
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!