题意：

N个数，M组询问，每次问[l,r]中有多少个数出现正偶数次。

思路：

把N个数分成sqrt(n)块，预处理d[i][j]表示第i块起点到第j块末尾的答案

枚举起点i，并维护一个数组记录每个数到目前为止出现的次数，从偶变奇、从奇变偶时相应增减答案。

把每个数在数列中出现的位置从小到大排序后放入到一个数组Arr中备用。

读入每个询问[l,r]。如果l和r在同一个块中暴力即可，否则设l所在块的末尾为l’，r所在块的起点为r’，[l’+1,r’-1]的答案已经预处理出。扫描l~l’, r’~r的所有数，统计每个数出现的次数cnt，第一次出现时把它加入队列。

对于队列中的每个数，在数组Arr中二分l’+1和r’-1，得到在[l’+1,r’-1]中出现的次数k。通过对k和当前队列中的数的cnt进行奇偶性讨论更新答案

（from lyd的题解…）

我们就可以vector +lower_bound()

搞定~

（也可以用可持久化线段树之类的东西…）

最后 　祝他们幸福……

//By SiriusRen

#include <cmath>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=100005;

int n,c,m,a[N],Block,block[N],f[1111][1111],vis[N],ans,l,r,stk[N],top;

vector<int>vec[N];

int main(){

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

    for(int i=1;i<=n;i++)scanf("%d",&a[i]),block[i]=(i-1)/Block+1,vec[a[i]].push_back(i);

    for(int i=1;i<=block[n];i++){

        memset(vis,0,sizeof(vis));int temp=0;

        for(int j=lower_bound(block,block+1+n,i)-block;j<=n;j++){

            vis[a[j]]++;

            if(vis[a[j]]%2==0)temp++;

            else if(vis[a[j]]!=1)temp--;

            if(block[j]!=block[j+1])f[i][block[j]]=temp;

        }

    }

    memset(vis,0,sizeof(vis));

    for(int i=1;i<=m;i++){

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

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

        if(l>r)swap(l,r);ans=0;

        int L=block[l]+1,R=block[r];

        if(L<R){

            int ll=lower_bound(block+1,block+1+n,L)-block-1;

            int rr=lower_bound(block+1,block+1+n,R)-block;

            R--;top=0;

            for(int i=l;i<=ll;i++)vis[a[i]]++,stk[++top]=a[i];

            for(int i=rr;i<=r;i++)vis[a[i]]++,stk[++top]=a[i];

            ans=f[L][R];

            for(int i=1;i<=top;i++)if(vis[stk[i]]){

                int t=lower_bound(vec[stk[i]].begin(),vec[stk[i]].end(),rr)-

                lower_bound(vec[stk[i]].begin(),vec[stk[i]].end(),ll+1);

                if(!t){if(vis[stk[i]]%2==0)ans++;}

                else if(t%2==0){if(vis[stk[i]]%2==1)ans--;}

                else if(t%2==1&&vis[stk[i]]%2==1)ans++;

                vis[stk[i]]=0;

            }

        }

        else{

            top=0;

            for(int i=l;i<=r;i++)vis[a[i]]++;

            for(int i=l;i<=r;i++)if(vis[a[i]]){

                if(vis[a[i]]%2==0)ans++;

                vis[a[i]]=0;

            }

        }

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

    }

}