记录编号	593306	评测结果	AAAAAAAAAA
题目名称	[BZOJ 2821]作诗	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	8.742 s
提交时间	2024-08-29 18:43:54	内存使用	35.08 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define MAXM 1010
#define debug() cout<<"I LOVE COGS\n"
int t,n,c,m,len,ql,qr,ans;
int l[MAXM],r[MAXM],g[MAXN],cnt[MAXM][MAXN],f[MAXM][MAXM],re[MAXN],a[MAXN]; 
int main(){
    freopen("poetize.in","r",stdin);
    freopen("poetize.out","w",stdout);
    cin>>n>>c>>m;
    len=sqrt(n);
    t=(n-1)/len+1;
//    cout<<<<len<<endl;
    for(int i=1;i<=t;i++){
        l[i]=(i-1)*len+1;
        r[i]=min(i*len,n);
    }
    for(int i=1;i<=n;i++)cin>>a[i]; 
    for(int i=1;i<=t;i++){
        for(int j=i;j;j--){
            f[j][i]=f[j+1][i];
            for(int u=l[j];u<=r[j];u++){
//                g[u]=i;
                if(j==i)g[u]=i;
                cnt[i][a[u]]++;
                if(cnt[i][a[u]]%2==0)f[j][i]++;
                else if(cnt[i][a[u]]>1)f[j][i]--;   
            }
        }
    }
    for(int i=1;i<=m;i++){
        cin>>ql>>qr;
        ql=(ql+ans)%n+1,qr=(qr+ans)%n+1;
        if(ql>qr)swap(ql,qr);
        int L=g[ql],R=g[qr];
        if(L==R){
//            debug();
            ans=0;
            for(int j=ql;j<=qr;j++){
                re[a[j]]++;
                if(re[a[j]]%2==0)ans++;
                else if(re[a[j]]>1)ans--;
            }
            for(int j=ql;j<=qr;j++)re[a[j]]--;
//            debug();
        }else{
            ans=f[L+1][R-1];
            for(int j=ql;j<=r[L];j++){
                re[a[j]]++;
                if((cnt[R-1][a[j]]-cnt[L][a[j]]+re[a[j]])%2==0&&(cnt[R-1][a[j]]-cnt[L][a[j]]+re[a[j]]))ans++;
                else if(cnt[R-1][a[j]]-cnt[L][a[j]]+re[a[j]]>1)ans--;
            }
            for(int j=l[R];j<=qr;j++){
                re[a[j]]++;
                if((cnt[R-1][a[j]]-cnt[L][a[j]]+re[a[j]])%2==0&&(cnt[R-1][a[j]]-cnt[L][a[j]]+re[a[j]]))ans++;
                else if(cnt[R-1][a[j]]-cnt[L][a[j]]+re[a[j]]>1)ans--;
            }
//            debug();
            for(int j=ql;j<=r[L];j++){
                re[a[j]]--;
            }
            for(int j=l[R];j<=qr;j++){
                re[a[j]]--;
            }
//            debug();
        }
        cout<<ans<<endl;
//        debug();
    }
    return 0;
}