813E - Army Creation - CodeForces Solution

// Persistent Segment Tree

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define dbg(a)  cerr << #a << ": " << a << "\n"

const int N = 1e5+5;

struct node {
  int s, l, r;
  node (int s = 0, int l = -1, int r = -1): s(s), l(l), r(r) {}
}st[40 * N];

int idx;

int add(int u, int i, int x, int s = 0, int e = N - 1) {
  if (s == e) {
    st[idx++] = {st[u].s + x, st[u].l, st[u].r};
    return idx - 1;
  }
  if (st[u].l == -1)  st[u].l = idx++, st[u].r = idx++;
  int nu = idx++;
  st[nu] = st[u];

  int m = (s + e) / 2;
  if (i <= m)  st[nu].l = add(st[nu].l, i, x, s, m);
  else st[nu].r = add(st[nu].r, i, x, m + 1, e);
  st[nu].s = st[st[nu].l].s + st[st[nu].r].s;
  return nu;
}

int rsum(int u, int l, int r, int s = 0, int e = N - 1) {
  if (u == -1)  return 0;
  if (s > r or e < l)  return 0;
  if (l <= s and e <= r)  return st[u].s;
  int m = (s + e) / 2;
  return rsum(st[u].l, l, r, s, m) + rsum(st[u].r, l, r, m + 1, e);
}

void solve() {
  int n, k;  cin >> n >> k;
  vector<int> a(n);
  for (auto &ai: a) {
    cin >> ai;
  }
  vector<int> pos[N];
  vector<int> roots(n + 1);
  roots[0] = idx++;
  for (int i = 0; i < n; ++i) {
    roots[i + 1] = add(roots[i], i, 1);
    pos[a[i]].push_back(i);
    int sz = pos[a[i]].size();
    if (sz > k) {
      roots[i + 1] = add(roots[i + 1], pos[a[i]][sz - k - 1], -1);
    }
  }

  int q;  cin >> q;
  int last = 0;
  while (q--) {
    int l, r;  cin >> l >> r;
    l = (l + last) % n + 1;
    r = (r + last) % n + 1;
    if (l > r)  swap(l, r);
    l--, r--;
    last = rsum(roots[r + 1], l, r);
    cout << last << "\n";
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);

  int tc = 1;
  for (int t = 1; t <= tc; ++t) {
    solve();
  }
}