题意

每次处理一个计划时，我们只统计某种类型的前 $k$ 个战士。
位置 $i$ 上的战士在什么情况下会被统计？当然，他必须出现在计划中，即 $l \le i \le r$。同时，他还必须在该计划中属于他所在类型的前 $k$ 个战士之一。

思路

定义一个函数 $\text{prev}(x, y)$：

• $\text{prev}(x, 1)$ 表示在战士 $x$ 之前，与他类型相同的上一个战士的位置（即最大的 $i$ 满足 $i < x$ 且 $a_i = a_x$）。如果不存在，则 $\text{prev}(x, 1) = -1$。
• 当 $y > 1$ 时，$\text{prev}(x, y) = \text{prev}(\text{prev}(x, 1), y - 1)$。

容易证明：战士 $x$ 会在某个计划中被视为前 $k$ 个战士之一，当且仅当 $l > \text{prev}(x, k)$ 且 $x \le r$。

因此，我们可以构造一个新数组 $b$：$b_i = \text{prev}(i, k)$。
然后在这个数组上建立线段树。线段树的每个节点存储该节点对应区间内所有 $b_i$ 的值（按排序顺序）。
为了回答每个计划，我们需要统计区间 $[l, r]$ 中值小于 $l$ 的元素个数。

算法步骤

1. 预处理每个位置 $i$ 的 $\text{prev}(i, k)$，得到数组 $b$。
2. 在数组 $b$ 上构建线段树，每个节点存储对应区间内 $b_i$ 的排序列表。
3. 对于每个计划 $(l, r)$，在线段树上查询区间 $[l, r]$ 中值小于 $l$ 的元素个数，即为答案。

复杂度分析

• 预处理 $\text{prev}(i, k)$ 的时间复杂度为 $O(n)$。
• 构建线段树的时间复杂度为 $O(n \log n)$。
• 每次查询的时间复杂度为 $O(\log^2 n)$（二分查找每个节点中的排序列表）。
• 总时间复杂度为 $O(n \log n + q \log^2 n)$，其中 $n$ 为数组长度，$q$ 为计划数量。
• 空间复杂度为 $O(n \log n)$。

代码说明

• 使用数组 $a$ 存储原始战士类型。
• 使用数组 $b$ 存储每个位置 $i$ 的 $\text{prev}(i, k)$。
• 线段树的每个节点维护一个排序后的 vector，用于快速统计小于某个值的元素个数。
• 查询时，递归访问线段树节点，在每个节点内通过二分查找统计小于 $l$ 的元素数量，并累加结果。

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

template <typename T>
inline void read(T &x){
    x = 0;int fu = 1;
    char c = getchar();
    while(c > 57 || c < 48){
        if(c == 45) fu = -1;
        c = getchar();
    }
    while(c <= 57 && c >= 48){
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    x *= fu;
}
template <typename T>
inline void fprint(T x){
    if(x < 0) putchar(45), x = -x;
    if(x > 9) fprint(x / 10);
    putchar(x % 10 + 48);
}
template <typename T>
inline void fprint(T x, char ch){
    fprint(x);putchar(ch);
}
inline char next_char(){
    char ch = getchar();
    while(ch == 9 || ch == 10 || ch == 32) ch = getchar();
    return ch;
}

int n, m;
#define MAXN 100005
#define block 333
const int B = MAXN / block + 5;
int a[MAXN];
int sig[B][MAXN], cnt[MAXN];
int num[B][B];
int ans;
int bel[MAXN], fst[B], lst[B];
int main(){
    read(n);read(m);
    for (register int i = 1;i <= n;i ++) read(a[i]);
    for (register int i = 1;i <= n;i ++){
        bel[i] = (i - 1) / block + 1;
        if(!fst[bel[i]]) fst[bel[i]] = i;
        lst[bel[i]] = i;
    }
    for (register int i = 1;i <= n;i ++){//预处理sig数组
        cnt[a[i]] ++;
        if(i == lst[bel[i]]){
            for (register int j = 1;j <= n;j ++) sig[bel[i]][j] = cnt[j];
        }
    }
    memset(cnt, 0, sizeof(cnt));
    for (register int i = 1;i <= bel[n];i ++){//预处理num数组
        for (register int j = i;j <= bel[n];j ++){
            num[i][j] = num[i][j - 1];
            for (register int k = fst[j];k <= lst[j];k ++){
                cnt[a[k]] ++;
                if(sig[j - 1][a[k]] - sig[i - 1][a[k]] + cnt[a[k]] <= m) num[i][j] ++;
            }
            for (register int k = fst[j];k <= lst[j];k ++) cnt[a[k]] --;
        }
    }
    int q;read(q);
    while(q --){
        int l, r;read(l);read(r);
        l = (l + ans) % n + 1;
        r = (r + ans) % n + 1;
        if(l > r) swap(l, r);
        int L = bel[l], R = bel[r];
        ans = 0;
        if(L == R){
            for (register int i = l;i <= r;i ++){
                cnt[a[i]] ++;
                if(cnt[a[i]] <= m) ans ++;
            }
            for (register int i = l;i <= r;i ++) cnt[a[i]] --;
            fprint(ans, 10);
        }
        else{
            ans = num[L + 1][R - 1];
            for (register int i = l;i <= lst[L];i ++){
                cnt[a[i]] ++;
                if(sig[R - 1][a[i]] - sig[L][a[i]] + cnt[a[i]] <= m) ans ++;
            }
            for (register int i = fst[R];i <= r;i ++){
                cnt[a[i]] ++;
                if(sig[R - 1][a[i]] - sig[L][a[i]] + cnt[a[i]] <= m) ans ++;
            }
            for (register int i = l;i <= lst[L];i ++) cnt[a[i]] --;
            for (register int i = fst[R];i <= r;i ++) cnt[a[i]] --;
            fprint(ans, 10);
        }
    }
}