Codeforces 813E Army Creation

不强制在线的话，莫队？
强制在线，分块？

等等 k 是常数？
好像有点东西。

发现 k 是常数，所以可以考虑预处理出每个数往前 k 个同样的数的位置，如果前面的数不足 k 个就当成 0。
对于 ai，记这个位置为 prei。

把所有数当成二维上的点 (i,prei)，问题变成了询问矩形 (l,0)∼(r,l−1) 内的点的个数。
如果离线可以树状数组处理。

强制在线的话，相比树套树而言，静态问题可以用常数更小并且只有一个 log 的主席树来处理。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int C = 1e5;
int n,k,q;
int a[N + 5],pre[N + 5],lastans;
vector<int> pos[C + 5];
struct node
{
    int sum;
    int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5];
void insert(int x,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    seg[++tot] = seg[p],p = tot;
    seg[p].sum += k;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    if(x <= mid)
        insert(x,k,seg[p].ls,tl,mid);
    else
        insert(x,k,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].sum;
    int mid = tl + tr >> 1;
    int ret = 0;
    if(l <= mid)
        ret += query(l,r,seg[p].ls,tl,mid);
    if(r > mid)
        ret += query(l,r,seg[p].rs,mid + 1,tr);
    return ret;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),insert(pre[i] = pos[a[i]].size() >= k ? pos[a[i]][pos[a[i]].size() - k] : 0,1,rt[i] = rt[i - 1],0,n),pos[a[i]].push_back(i);
    scanf("%d",&q);
    int l,r;
    while(q--)
    {
        scanf("%d%d",&l,&r),l = (l + lastans) % n + 1,r = (r + lastans) % n + 1;
        if(l > r)
            swap(l,r);
        printf("%d\n",lastans = query(0,l - 1,rt[r],0,n) - query(0,l - 1,rt[l - 1],0,n));
    }
}