P4135 作诗——分块

题目：https://www.luogu.org/problemnew/show/P4135

分块大法；

块之间记录答案，每一块记录次数前缀和；

注意每次把桶中需要用到位置赋值就好了；

为什么加了特判会 T 一个点?

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int const maxn=1e5+;

int n,c,m,mod,a[maxn],ans,blk[maxn],base,t[maxn],cnt[][maxn],bst[],bed[],f[][];

void pre(int x)

{

    int tmp=,tem=x;

    memset(t,,sizeof t);

    for(int i=bst[x];i<=n;i++)

    {

        t[a[i]]++;

        if(t[a[i]]%==)tmp++;

        else if(t[a[i]]>)tmp--;

        if(i==bed[tem])f[x][tem]=tmp,tem++;

    }

}

int main()

{

    scanf("%d%d%d",&n,&c,&m);

    base=sqrt(n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]),blk[i]=(i-)/base+;

    for(int i=;i<=blk[n];i++)bst[i]=(i-)*base+,bed[i]=min(n,i*base);

    for(int i=;i<=blk[n];i++)pre(i);

    for(int i=;i<=blk[n];i++)

    {

        for(int k=;k<=c;k++)cnt[i][k]=cnt[i-][k];

        for(int j=bst[i];j<=bed[i];j++)cnt[i][a[j]]++;

    }

    for(int i=,l,r;i<=m;i++)

    {

        scanf("%d%d",&l,&r);

        l=(l+ans)%n+; r=(r+ans)%n+;

        if(l>r)swap(l,r);

//        if(l==r){printf("0\n"); ans=0; continue;}//ans=0!!!  //加特判变慢了???

        ans=;

        if(blk[l]==blk[r])

        {

            for(int j=l;j<=r;j++)t[a[j]]=;

            for(int j=l;j<=r;j++)

            {

                t[a[j]]++;

                if(t[a[j]]%==)ans++;

                else if(t[a[j]]>)ans--;

            }

            printf("%d\n",ans);

        }

        else

        {

            if(blk[r]>blk[l]+)ans=f[blk[l]+][blk[r]-];

            for(int j=l;j<=bed[blk[l]];j++)t[a[j]]=cnt[blk[r]-][a[j]]-cnt[blk[l]][a[j]];

            for(int j=bst[blk[r]];j<=r;j++)t[a[j]]=cnt[blk[r]-][a[j]]-cnt[blk[l]][a[j]];

            for(int j=l;j<=bed[blk[l]];j++)

            {

                t[a[j]]++;

                if(t[a[j]]%==)ans++;

                else if(t[a[j]]>)ans--;

            }

            for(int j=bst[blk[r]];j<=r;j++)

            {

                t[a[j]]++;

                if(t[a[j]]%==)ans++;

                else if(t[a[j]]>)ans--;

            }

            printf("%d\n",ans);

        }

    }

    return ;

}