题目连接：Codeforces - 813E - Army Creation
区间 [L,R] 内，如果一个数可以被选的话，那么它在当前区间内与它的值相同的所有数字中，它的顺序应该要小于等于 k 的。我们创建一个 b 数组， b[i] 表示当前数的往前第 k 个值相同的数的位置。 这样，如果一个数 a[i] 能被选是 b[i]<L 的充要条件。 这样问题就转化为求一个区间内有多少数小于 L 。
如果是离线的话，可以用莫队来做，复杂度是 O(n1.5) 。 但是这题强制在线。强制在线分块的话有 O(n1.5logn) 的算法。考虑到 ai≤105 。因此可以对每一块维护一个前缀和。这样就可以做到 O(n1.5) 了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+7; vector<int> order[N]; int n,k; int dp[350][N],p[N],a[N],b[N]; struct Block { int l,r; }; Block bl[350]; int main() { ios::sync_with_stdio(false); cin >> n >> k; int len=(int)sqrt(n); int sz=(n-1)/len+1; for(int i=1;i<=n;i++) { int t,v; cin>>t; a[i]=t; if(order[t].size()>=k) b[i]=order[t][order[t].size()-k]; else b[i]=0; order[t].push_back(i); v=b[i]; p[i]=(i-1)/len+1; if(!bl[p[i]].l) bl[p[i]].l=i; bl[p[i]].r=i; ++dp[p[i]][v]; } for(int i=1;i<=sz;i++) for(int j=1;j<=n;j++) dp[i][j]+=dp[i][j-1]; int q,ans=0,l,r; cin >> q; while(q--) { cin >> l >> r; l=(l+ans)%n+1; r=(r+ans)%n+1; ans=0; if(l>r) swap(l,r); if(p[l]==p[r]) { for(int i=l;i<=r;i++) if(b[i]<l) ans++; } else { for(int i=l;i<=bl[p[l]].r;i++) if(b[i]<l) ans++; for(int i=bl[p[r]].l;i<=r;i++) if(b[i]<l) ans++; for(int i=p[l]+1;i<p[r];i++) ans+=dp[i][l-1]; } cout << ans << endl; } return 0; }