题目链接：Codeforces 813E

Vova 非常喜欢玩电脑游戏，现在他正在玩一款叫做 Rage of Empires 的策略游戏。

在这个游戏里，Vova 可以雇佣 $n$ 个不同的战士，第 $i$ 个战士的类型为 $a_i$。Vova 想要雇佣其中一些战士，从而建立一支平衡的军队。如果对于任何一种类型，军队中这种类型的战士都不超过 $k$，那么这支军队就被称为平衡的。当然 Vova 想让这支军队的人数尽量多。

现在 Vova 有 $q$ 个计划，第 $i$ 个计划他只能雇佣区间 $[l_i,r_i]$ 之间的战士。对于每个计划，你需要求出可以组建的平衡军队的最多人数。

本题强制在线，对于给定的 $l_i,r_i$，我们设上一个计划的答案为 $\text{lastans}$（初始值为 $0$），实际的 $l_i,r_i$ 通过如下方式生成：

1. $l_i \leftarrow ((l_i + \text{lastans})\bmod n) + 1$。
2. $r_i \leftarrow ((r_i + \text{lastans})\bmod n) + 1$。
3. 如果 $l_r>r_i$，交换 $l_i$ 和 $r_i$。

数据范围：$1\le n,k,q,a_i\le 10^5$。

Solution

由于 $k$ 是给定的，我们设第 $i$ 个元素往后数 $k$ 个和它相同的元素到达的位置为 $b_i$；特殊地，如果第 $i$ 个数后面和它相同的数字少于 $k$ 个，那么 $b_i = n + 1$。

简单观察可以发现，我们要统计的就是区间 $[l,r]$ 内有多少个 $b_i$ 满足 $b_i > r$。

直接对 $b_i$ 建立主席树，统计区间内权值范围在 $[r+1, n+1]$ 的数的个数即可。

时间复杂度：$\mathcal O((n + q) \log n)$。

Code

#include <cstdio>
#include <algorithm>
#include <vector>

const int N = 1e5 + 5;

int n, m, k, a[N], nxtk[N];
std::vector<int> v[N];

struct Chairman {
    static const int M = 20 * N;
    int idx, rt[N], ls[M], rs[M], sum[M];
    void modify(int &p, int l, int r, int u, int x, int v) {
        p = ++idx, ls[p] = ls[u], rs[p] = rs[u], sum[p] = sum[u] + v;
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) {
            modify(ls[p], l, mid, ls[u], x, v);
        } else {
            modify(rs[p], mid + 1, r, rs[u], x, v);
        }
    }
    int query(int p, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            return sum[p];
        }
        int mid = (l + r) >> 1;
        if (y <= mid) {
            return query(ls[p], l, mid, x, y);
        } else if(x > mid) {
            return query(rs[p], mid + 1, r, x, y);
        } else {
            return query(ls[p], l, mid, x, mid) + query(rs[p], mid + 1, r, mid + 1, y);
        }
    }
} cha;

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = n; i >= 1; i--) {
        int sz = v[a[i]].size();
        if (sz < k) {
            nxtk[i] = n + 1;
        } else {
            nxtk[i] = v[a[i]][sz - k];
        }
        v[a[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        cha.modify(cha.rt[i], 1, n + 1, cha.rt[i - 1], nxtk[i], 1);
    }
    scanf("%d", &m);
    for (int lastans = 0, i = 1; i <= m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        l = (l + lastans) % n + 1;
        r = (r + lastans) % n + 1;
        if (l > r) std::swap(l, r);
        int R = cha.query(cha.rt[r], 1, n + 1, r + 1, n + 1);
        int L = cha.query(cha.rt[l - 1], 1, n + 1, r + 1, n + 1);
        printf("%d\n", lastans = R - L);
    }
    return 0;
}