关于我的分块常数堪比LCT这档事

考虑分块.预处理$sum(i,j)$表示$[1,i]$所有块中颜色$j$的数量.时间复杂度$\mathcal O(c\sqrt n)$.
预处理$f(i,j)$表示第$i$个块到第$j$个块的答案.时间复杂度$\mathcal O(n\sqrt n)$

询问时,若$l,r$所在块相同或相邻,则暴力.否则暴力$l$所在块和$r$所在块,并合并中间部分.每次询问时间复杂度$\mathcal O(\sqrt n)$
总时间复杂度$\mathcal O((n+c+m)\sqrt n)$.

/**********/
const ll MAXN=100011,MAXB=311,M=400;
ll sum[MAXB][MAXN],f[MAXB][MAXB],cnt[MAXN];
ll a[MAXN];
ll n,c,m;
void prework()
{
    for(ll i=1;i<=n;++i)
    {
        ll B=(i-1)/M+1;
        if((i-1)%M==0)
        {
            for(ll j=1;j<=c;++j)sum[B][j]=sum[B-1][j];
        }
        ++sum[B][a[i]];
    }
    for(ll i=1;i<=(n-1)/M+1;++i)
    {
        ll cur=0;
        for(ll j=(i-1)*M+1;j<=n;++j)
        {
            if(cnt[a[j]])
                if(cnt[a[j]]&1)++cur;
                else --cur;
            ++cnt[a[j]];
            if(j%M==0)f[i][(j-1)/M+1]=cur;
        }
        for(ll j=(i-1)*M+1;j<=n;++j)cnt[a[j]]=0;
    }
}
int main()
{
    n=read(),c=read(),m=read();
    for(ll i=1;i<=n;++i)a[i]=read();
    prework();
    ll ans=0;
    while(m--)
    {
        ll l=(read()+ans)%n+1,r=(read()+ans)%n+1;
        if(l>r)std::swap(l,r);
        ll Bl=(l-1)/M+1,Br=(r-1)/M+1;
        if(Bl+1>=Br)
        {
            ans=0;
            for(ll i=l;i<=r;++i)
            {
                if(cnt[a[i]])
                    if(cnt[a[i]]&1)++ans;
                    else --ans;
                ++cnt[a[i]];
            }
            printf("%d\n",ans);
            for(ll i=l;i<=r;++i)cnt[a[i]]=0;
        }
        else
        {
            ans=f[Bl+1][Br-1];
            for(ll i=l;i<=Bl*M;++i)
            {
                if(!cnt[a[i]])cnt[a[i]]=sum[Br-1][a[i]]-sum[Bl][a[i]];
                if(cnt[a[i]])
                    if(cnt[a[i]]&1)++ans;
                    else --ans;
                ++cnt[a[i]];
            }
            for(ll i=(Br-1)*M+1;i<=r;++i)
            {
                if(!cnt[a[i]])cnt[a[i]]=sum[Br-1][a[i]]-sum[Bl][a[i]];
                if(cnt[a[i]])
                    if(cnt[a[i]]&1)++ans;
                    else --ans;
                ++cnt[a[i]];
            }
            printf("%d\n",ans);
            for(ll i=l;i<=Bl*M;++i)cnt[a[i]]=0;
            for(ll i=(Br-1)*M+1;i<=r;++i)cnt[a[i]]=0;
        }
    }
    return 0;
}