題意： N個(gè)數(shù)，M組詢問(wèn)，每次問(wèn)[l,r]中有多少個(gè)數(shù)出現(xiàn)正偶數(shù)次。 思路： 把N個(gè)數(shù)分成sqrt(n)塊，預(yù)處理d[i][j]表示第i塊起點(diǎn)到第j塊末尾的答案 枚舉起點(diǎn)i，并維護(hù)一個(gè)數(shù)組記錄每個(gè)數(shù)到目前為止出現(xiàn)的次數(shù)，從偶變奇、從奇變偶時(shí)相應(yīng)增減答案。 把每個(gè)數(shù)在數(shù)列中出現(xiàn)的位置從小到大排序后放入到一個(gè)數(shù)組Arr中備用。 讀入每個(gè)詢問(wèn)[l,r]。如果l和r在同一個(gè)塊中暴力即可，否則設(shè)l所在塊的末尾為l’，r所在塊的起點(diǎn)為r’，[l’+1,r’-1]的答案已經(jīng)預(yù)處理出。掃描l~l’, r’~r的所有數(shù)，統(tǒng)計(jì)每個(gè)數(shù)出現(xiàn)的次數(shù)cnt，第一次出現(xiàn)時(shí)把它加入隊(duì)列。 對(duì)于隊(duì)列中的每個(gè)數(shù)，在數(shù)組Arr中二分l’+1和r’-1，得到在[l’+1,r’-1]中出現(xiàn)的次數(shù)k。通過(guò)對(duì)k和當(dāng)前隊(duì)列中的數(shù)的cnt進(jìn)行奇偶性討論更新答案

（from lyd的題解…）

我們就可以vector +lower_bound() 搞定~

（也可以用可持久化線段樹(shù)之類的東西…）

最后 　祝他們幸?！?/p>//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; } }