$O(N\sqrt(N))$做法
预处理出每一块到结尾每一种颜色的个数,以及块与块之间的答案。
每一次询问仅需$\sqrt(N)$的时间暴力拓展就好了。

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=1e5+10;
const int B=350;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int l[B],r[B],cnt[320][N],f[B][B],a[N],pos[N],c[N],sta[N],top;bool v[N];
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.ans","w",stdout);
    int n,C,m;qr(n),qr(C),qr(m);
    for(int i=1;i<=n;i++)qr(a[i]);
    int bl=sqrt(n),sz=bl;
    for(int i=1;i<=sz;i++)
    {
        l[i]=r[i-1]+1,r[i]=i*bl;
        for(int j=l[i];j<=r[i];j++)
            pos[j]=i;
    }
    if(r[sz]<n){l[sz+1]=r[sz]+1,r[++sz]=n;for(int i=l[sz];i<=r[sz];i++)pos[i]=sz;}
    for(int i=sz;i>=1;i--)
    {
        int num=0;
        for(int j=l[i];j<=n;j++)
        {
            ++cnt[i][a[j]];
            if((cnt[i][a[j]]&1)&&(cnt[i][a[j]]!=1))--num;//从2开始才计算 
            else if((cnt[i][a[j]]&1)==0)++num;
            if(pos[j]!=pos[j+1])
                f[i][pos[j]]=num;
        }
    }
    int ans=0;
    while(m--)
    {
        int L,R;qr(L),qr(R);L=(L+ans)%n+1,R=(R+ans)%n+1;
        if(L>R)swap(L,R);int p=pos[L],q=pos[R];
        if(p==q)
        {
            ans=0;
            for(int i=L;i<=R;i++)
            {
                ++c[a[i]];
                if((c[a[i]]&1)&&(c[a[i]]!=1))--ans;
                else if((c[a[i]]&1)==0)++ans;
            }
            for(int i=L;i<=R;i++)
                if(c[a[i]])c[a[i]]=0;
        }
        else
        {
            ans=f[p+1][q-1];
            for(int i=L;i<=r[p];i++)
            {
                ++c[a[i]];
                if(!v[a[i]])sta[++top]=a[i],v[a[i]]=1;
            }
            for(int i=l[q];i<=R;i++)
            {
                ++c[a[i]];
                if(!v[a[i]])sta[++top]=a[i],v[a[i]]=1;
            }
            while(top)
            {
                int x=sta[top--];
                if((cnt[p+1][x]-cnt[q][x])!=0&&((cnt[p+1][x]-cnt[q][x])&1)&&(c[x]&1))++ans;
                else if((cnt[p+1][x]-cnt[q][x])!=0&&(((cnt[p+1][x]-cnt[q][x])&1)==0)&&(c[x]&1))--ans;
                else if((cnt[p+1][x]-cnt[q][x])==0&&(c[x]!=0)&&((c[x]&1))==0)++ans;
                v[x]=0;c[x]=0;
            }
        }
        qw(ans);puts("");
    }
    return 0;
}