一、分块
核心就是找到分块要维护的东西。想象一列数字中，我们取出其中相同的一组，我们要在给定范围内取不超过k个，如果暴力从左往右判断然后记录个数，很不现实吧。那我们就开个数组记录这个数在此组中的位置+k个后会不会超过这一组的个数，但之后统计的关键不是“从左往右”。如果碰到的数+k后还在区间内，我们不做记录，因为这样限制条件就会很多，分块询问时中间的块也不好问，很容易出错（但说不定可以写）。我们可以转换思路，专找+k后大于边界的，这说明我们拿上它个数也不会超过k，这样ans++；之后分块，两边一个一个找，中间用二分找到大于边界的，直接加，所以前面要sort预处理。
//写得乱七八糟的题解，可能只有我自己才看得懂~~
1 #include<bits/stdc++.h> 2 #include<iostream> 3 #include<stack> 4 #include<algorithm> 5 #include<cstdio> 6 #include<cmath> 7 #include<cstring> 8 #define mem(a) memset(a,0,sizeof(a)) 9 #define mem1(a) memset(a,-1,sizeof(a)) 10 #define fio ios::sync_with_stdio(false);cin.tie(0) 11 #define ll long long 12 #define mp make_pair 13 #define inf 0x3f3f3f3f 14 const int N=1e5+5; 15 const int M=1e3+10; 16 const int mod=9973; 17 using namespace std; 18 int blo,num,belong[N],n,nx[N],l[N],a[N],b[N],r[N],k,mx=-inf; 19 vector<int>cnt[N]; 20 void build() 21 { 22 blo=sqrt(n); 23 num=(n%blo)? n/blo+1:n/blo; 24 for(int i=1;i<=n;i++) 25 { 26 belong[i]=(i-1)/blo+1; 27 b[i]=nx[i]; 28 } 29 for(int i=1;i<=num;i++) 30 { 31 l[i]=(i-1)*blo+1; 32 r[i]=i*blo; 33 } 34 r[num]=n; 35 for(int i=1;i<=num;i++) 36 sort(b+l[i],b+r[i]+1); 37 } 38 inline int query(int x,int y) 39 { 40 int ans=0; 41 for(int i=x;i<=min(r[belong[x]],y);i++) 42 if(nx[i]>y) ans++; 43 if(belong[x]!=belong[y]) 44 { 45 for(int i=l[belong[y]];i<=y;i++) 46 if(nx[i]>y) ans++; 47 for(int i=belong[x]+1;i<=belong[y]-1;i++) 48 { 49 int j=b+r[i]+1-upper_bound(b+l[i],b+r[i]+1,y); 50 ans+=j; 51 } 52 } 53 return ans; 54 } 55 int main() 56 { 57 cin>>n>>k; 58 for(int i=1;i<=n;i++) 59 { 60 cin>>a[i]; 61 cnt[a[i]].push_back(i); 62 mx=max(mx,a[i]); 63 } 64 for(int i=1;i<=mx;i++) 65 { 66 for(int j=0;j<cnt[i].size();j++) 67 { 68 if(j+k>=cnt[i].size()) nx[cnt[i][j]]=N; 69 else nx[cnt[i][j]]=cnt[i][j+k]; 70 } 71 } 72 build(); 73 int m,x,y,last=0; 74 cin>>m; 75 while(m--) 76 { 77 cin>>x>>y; 78 x=(x+last)%n+1; 79 y=(y+last)%n+1; 80 if(x>y) swap(x,y); 81 int ans; 82 if(y-x+1<=k) ans=y-x+1; 83 else ans=query(x,y); 84 cout<<ans<<endl; 85 last=ans; 86 } 87 return 0; 88 }