题解 P4135 【作诗】

分块

题意：

给定数列，m次询问[l_i,r_i]中，出现正偶数次的数的个数。

思路：

想到分块暴力。预处理出：

cnt[i][j] 为前i块中 j出现的次数，ans[i][j]为第i块到第j块中 出现偶数次的数的个数

我的变量：

代码里有详细注释，（个人觉得分块题用这种写法较其他题解更好写且不易错

#include<bits/stdc++.h>
using namespace std;
const int amou=1e5+90,sqt=1e3+90;
int l[amou],r[amou],pos[amou],len,num;
int a[amou],n,m,c,las;
int cnt[sqt][amou],ans[sqt][sqt];
int t[amou];

int query(int ll,int rr){
    int posl=pos[ll],posr=pos[rr];
    if(posl+1>=posr)//只有1个块或者2个块都可以直接暴力
    {
        int s=0;//答案，即出现偶数次的数的个数
        for(int i=ll;i<=rr;i++)
        {
            t[a[i]]++;//桶
            if(!(t[a[i]]&1)) s++;//说明在t[]在+1之前是奇数，所以这是一种新方案
            else if(t[a[i]]>=3) s--;//说明t[]在+1之前是偶数，并且之前的t[]>=2，故s需-1
        }
        for(int i=ll;i<=rr;i++) t[a[i]]--;//由于memset超时，所以直接撤销
        return s;
    }
    else
    {
        int s=ans[posl+1][posr-1];
        for(int i=ll;i<=r[posl];i++)
        {
            t[a[i]]++;
            int temp=cnt[posr-1][a[i]]-cnt[posl][a[i]];//a[i]在posl+1~posr-1这几个块中出现的次数 
            if(!((t[a[i]]+temp)&1))  s++;
            else if(t[a[i]]+temp>=3) s--;
        }
        for(int i=l[posr];i<=rr;i++)
        {
            t[a[i]]++;
            int temp=cnt[posr-1][a[i]]-cnt[posl][a[i]];
            if(!((t[a[i]]+temp)&1))  s++;
            else if(t[a[i]]+temp>=3) s--;
        }
        for(int i=ll;i<=r[posl];i++) t[a[i]]--;
        for(int i=l[posr];i<=rr;i++) t[a[i]]--;
        return s;
    }
}

int main(){
    scanf("%d%d%d",&n,&c,&m);
    len=sqrt(n);
    num=ceil(n*1.0/len);
    for(int i=1;i<=num;i++)
    {
        l[i]=(i-1)*len+1;
        r[i]=i*len;
    }
    r[num]=n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        pos[i]=(i-1)/len+1;
        cnt[pos[i]][a[i]]++;
    }
    for(int i=1;i<=num;i++)
        for(int j=0;j<=c;j++)
            cnt[i][j]+=cnt[i-1][j];//累加前缀和 
    for(int i=1;i<=num;i++)//固定块i
    {
        for(int j=i;j<=num;j++)枚举右端块j
        {
            ans[i][j]=ans[i][j-1];//作为初始值
            for(int k=l[j];k<=r[j];k++)//枚举块j的左右端点
            {
                t[a[k]]++;
                if(!(t[a[k]]&1)) ans[i][j]++;
                else if(t[a[k]]>=3) ans[i][j]--;
            }
        }
        memset(t,0,sizeof t);//桶用完清零
    }
    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        int L=(l+las)%n+1,R=(r+las)%n+1;
        if(L>R) swap(L,R);
        int as=query(L,R);
        printf("%d\n",as);
        las=as;
    }
    return 0;
}