zcmimi's blog
avatar
zc
2020-10-10 17:22:12
  • 本文总阅读量

查看原题

点击跳转

预处理出

  • s[i][j]表示前i块到中j出现的次数
  • b[i][j]表示第i块到第j块的答案

统计时,在块内答案的基础上,枚举块外元素更新即可

#include<bits/stdc++.h>
const int N=100011;
int n,c,m,a[N],blk,bl[N],L[N],R[N],b[320][320],v[N],s[320][N];
int calc(int x){return x==1?0:x&1?-1:1;}
int solve(int l,int r){
    int res=0;
    if(bl[r]-bl[l]<=2){
        for(int i=l;i<=r;++i)v[a[i]]=0;
        for(int i=l;i<=r;++i)res+=calc(++v[a[i]]);
        return res;
    }
    res=b[bl[l]+1][bl[r]-1];
    for(int i=l;bl[i]==bl[l];++i)v[a[i]]=0;
    for(int i=r;bl[i]==bl[r];--i)v[a[i]]=0;
    for(int i=l;bl[i]==bl[l];++i)
        res+=calc(++v[a[i]]+s[bl[r]-1][a[i]]-s[bl[l]][a[i]]);
    for(int i=r;bl[i]==bl[r];--i)
        res+=calc(++v[a[i]]+s[bl[r]-1][a[i]]-s[bl[l]][a[i]]);
    return res;
}
int main(){
    scanf("%d%d%d",&n,&c,&m);blk=sqrt(n);
    for(int i=1;i<=n;++i)scanf("%d",a+i),bl[i]=(i-1)/blk+1;
    for(int i=1;i<=bl[n];++i)
        L[i]=R[i-1]+1,R[i]=R[i-1]+blk;
    R[bl[n]]=n;
    for(int i=1;i<=bl[n];++i){
        memset(v,0,sizeof v);
        for(int j=i,res=0;j<=bl[n];++j){
            for(int k=L[j];k<=R[j];++k)res+=calc(++v[a[k]]);
            b[i][j]=res;
        }

        for(int j=1;j<=c;++j)s[i][j]=s[i-1][j];
        for(int k=L[i];k<=R[i];++k)++s[i][a[k]];
    }
    int la=0,l,r;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&l,&r),l=(l+la)%n+1,r=(r+la)%n+1;
        if(l>r)std::swap(l,r);
        printf("%d\n",la=solve(l,r));
    }
}
LG 4135 作诗
comment评论
Search
search