不强制在线的话，莫队？
强制在线，分块？
等等 \(k\) 是常数？
好像有点东西。
发现 \(k\) 是常数，所以可以考虑预处理出每个数往前 \(k\) 个同样的数的位置，如果前面的数不足 \(k\) 个就当成 \(0\)。
对于 \(a_i\)，记这个位置为 \(pre_i\)。
把所有数当成二维上的点 \((i,pre_i)\)，问题变成了询问矩形 \((l,0) \sim (r,l - 1)\) 内的点的个数。
如果离线可以树状数组处理。
强制在线的话，相比树套树而言，静态问题可以用常数更小并且只有一个 \(\log\) 的主席树来处理。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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));
}
}