Army Creation

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


template<typename T>
class persistent_segtree
{
public:

    int n, m;
    vector<int> root, lc, rc;
    vector<T> st;
    int FREE_ID = 0;

    persistent_segtree() {}

    persistent_segtree(int n_, int m_, T val = T())
    {
        n = n_;
        m = m_;
        FREE_ID = 0;
        root.resize(n + 2);
        st.resize(m + 2, val);
        lc.resize(m + 2);
        rc.resize(m + 2);
    }

    T merge(T a, T b)
    {
        T res = a + b;
        return res;
    }

    int build(int l, int r) // create one dummy tree
    {
        int node = ++FREE_ID;
        if (l == r)
        {
            return node;
        }
        int mid = (l + r) >> 1;
        lc[node] = build(l, mid);
        rc[node] = build(mid + 1, r);
        return node;
    }

    int update(int prev, int ss, int se, int pos, int val)
    {
        int node = ++FREE_ID;
        if (ss == se)
        {
            st[node] = val;
            return node;
        }
        lc[node] = lc[prev];
        rc[node] = rc[prev];
        int mid = (ss + se) >> 1;
        if (pos <= mid)
        {
            lc[node] = update(lc[prev], ss, mid, pos, val);
        }
        else
        {
            rc[node] = update(rc[prev], mid + 1, se, pos, val);
        }
        st[node] = merge(st[lc[node]], st[rc[node]]);
        return node;
    }

    T query(int node, int ss, int se, int qs, int qe)
    {
        if (qs > se || qe < ss)
        {
            return T();
        }
        if (qs <= ss && se <= qe)
        {
            return st[node];
        }
        int mid = (ss + se) >> 1;
        T res = merge(query(lc[node], ss, mid, qs, qe), query(rc[node], mid + 1, se, qs, qe));
        return res;
    }

};

const int N = 1e5 + 5;

int a[N], val[N];
vector<int> adj[N];
int n, k, q;
persistent_segtree<int> obj;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        adj[a[i]].push_back(i);
        int sz = adj[a[i]].size();
        val[i] = 0;
        if (sz > k)
        {
            val[i] = adj[a[i]][sz - k - 1];
        }
    }

    cin >> q;
    int sz1 = n << 1;
    int sz2 = (log2(n) + 1) * (sz1 + 1);
    sz2 <<= 1;
    obj = persistent_segtree<int> (sz1, sz2);
    obj.root[0] = obj.build(1, n);

    for (int i = 1; i <= n; i++)
    {
        obj.root[i] = obj.update(obj.root[i - 1], 1, n, i, +1);
        if (val[i])
        {
            obj.root[i] = obj.update(obj.root[i], 1, n, val[i], 0);
        }
    }


    int last = 0;
    for (int i = 1; i <= q; i++)
    {
        int x, y;
        cin >> x >> y;
        int l = ((x + last) % n) + 1;
        int r = ((y + last) % n) + 1;
        if (l > r)
        {
            swap(l, r);
        }
        last = obj.query(obj.root[r], 1, n, l, r);
        cout << last << endl;
    }

    return 0;
}