记录编号	587577	评测结果	AAAAAAAAAA
题目名称	[BZOJ 2821]作诗	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	6.625 s
提交时间	2024-04-09 22:20:41	内存使用	202.44 MiB

#include <bits/stdc++.h>
using namespace std;
//分块大法好 
#define ll long long
const int N = 1e5+10,M = 510;
int n,C,m;
int a[N],c[N],s[M][M],cnt[N][M];
int L[M],R[M],bl[N],B,t,las;


void prework(){
    B = sqrt(n);t = (n-1)/B+1;
    for(int i = 1;i <= t;i++)L[i] = (i-1)*B+1,R[i] = min(i*B,n);
    for(int i = 1;i <= n;i++)bl[i] = (i-1)/B+1;
    
    for(int i = 1;i <= t;i++){
        for(int j = i;j <= t;j++){
            int sum = s[i][j-1];
            for(int k = L[j];k <= R[j];k++){
                c[a[k]]++;
                if(c[a[k]] % 2 == 0)sum++;
                else if(c[a[k]] != 1)sum--;
            }
            s[i][j] = sum;
//        cout<<i<<' '<<j<<' '<<s[i][j]<<endl;
        }
        for(int j = L[i];j <= n;j++)c[a[j]]--;
    }//预处理s数组 
    
    for(int i = 1;i <= t;i++){
        for(int j = 1;j <= C;j++)cnt[j][i] += cnt[j][i-1];
        for(int j = L[i];j <= R[i];j++)cnt[a[j]][i]++; 
    }//预处理cnt数组 
}
int ask(int l,int r){
    int p = bl[l],q = bl[r];
    if(p == q){
        int sum = 0;
        for(int i = l;i <= r;i++){
            c[a[i]]++;
            if(c[a[i]] % 2 == 0)sum++;
            else if(c[a[i]] != 1)sum--;
        }
        for(int i = l;i <= r;i++)c[a[i]]--;
        return sum;
    }
    int sum = s[p+1][q-1];
    for(int i = l;i <= R[p];i++){
        c[a[i]]++;
        if((c[a[i]]+cnt[a[i]][q-1]-cnt[a[i]][p]) % 2 == 0)sum++;
        else if(c[a[i]]+cnt[a[i]][q-1]-cnt[a[i]][p] != 1)sum--;
    }
    for(int i = L[q];i <= r;i++){
        c[a[i]]++;
        if((c[a[i]]+cnt[a[i]][q-1]-cnt[a[i]][p]) % 2 == 0)sum++;
        else if(c[a[i]]+cnt[a[i]][q-1]-cnt[a[i]][p] != 1)sum--;
    }
    for(int i = l;i <= R[p];i++)c[a[i]]--;
    for(int i = L[q];i <= r;i++)c[a[i]]--;
    return sum;
}
int main(){
	freopen("poetize.in","r",stdin);
    freopen("poetize.out","w",stdout);
    scanf("%d%d%d",&n,&C,&m);
    for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
    prework();
    for(int i = 1;i <= m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        l = (l + las) % n + 1,r = (r + las) % n + 1;
        if(l > r)swap(l,r);
        printf("%d\n",las=ask(l,r));
    }

	return 0;

}