原文链接：https://blog.csdn.net/nixinyis/java/article/details/68075234
神犇SJY虐完HEOI之后给傻×LYD出了一题：SHY是T国的公主，平时的一大爱好是作诗。由于时间紧迫，SHY作完诗之后还要虐OI，于是SHY找来一篇长度为N的文章，阅读M次，每次只阅读其中连续的一段[l,r]，从这一段中选出一些汉字构成诗。因为SHY喜欢对偶，所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好（为了拿到更多的素材！）。于是SHY请LYD安排选法。LYD这种傻×当然不会了，于是向你请教……问题简述：N个数，M组询问，每次问[l,r]中有多少个数出现正偶
数次。
Input
输入第一行三个整数n、c以及m。表示文章字数、汉字的种类数、要选择M次。第二行有n个整数，每个数Ai在[1, c]间，代表一个编码为Ai的汉字。接下来m行每行两个整数l和r，设上一个询问的答案为ans(第一个询问时ans=0)，
令L=(l+ans)mod n+1, R=(r+ans)mod n+1，若L>R，交换L和R，则本次询问为[L,R]。
Output
输出共m行，每行一个整数，第i个数表示SHY第i次能选出的汉字的最多种类数。
Sample Input
5 3 5
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5
Sample Output
2
0
0
0
1
HINT
对于100%的数据，1<=n,c,m<=10^5
【题解】
本题和上面一题的套路是一样的。
用f[i][j]表示第i块到第j块中符合条件的数的个数。
对于一个询问l~r，中间大块x~y已经知晓，要做的就是看l-x和y-r之间的数对答案的影响。
用vector保存每个数的位置，分别统计除了大块外的那些数（不超过2*sqrt(n)个）在x~y中出现的次数t1，以及在l~r之间出现的次数t2，根据t1和t2的奇偶性判断对答案的影响。同样，统计t1、t2也需要在vector中二分。
注：对f[i][j]的预处理可以在O(n * sqrt(n))的时间完成。
同时，块的大小取sqrt(n/log n)时最优。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 100010
#define B 1505
using namespace std;
vector<int> pos[N];
int a[N],belong[N],L[B],R[B];
int n,bs;
int f[B+5][B+5],tmp[N];
bool vis[N];
void pre()
{
int tot;
for(int i = 1;i <= bs;i++)
{
for(int j = L[i];j <= n;j++)
tmp[a[j]] = 0;
tot = 0;
for(int j = L[i];j <= n;j++)
{
if(!(tmp[a[j]]&1) && tmp[a[j]] != 0)
//如果a[j]出现次数为偶数次，非零，然后现在要从偶数次变成奇数次了
//于是tot变小
tot--;
tmp[a[j]]++;
if(!(tmp[a[j]]&1) )
//如果偶数
tot++;
f[i][belong[j]] = tot;
//f[i][j]表示第i块到第j块中符合条件的数的个数
}
}
}
int sigma(int l,int r,int x)
{
return max(upper_bound(pos[x].begin(),pos[x].end(),r)-lower_bound(pos[x].begin(),pos[x].end(),l),0);
}
int query(int l,int r)
{
int x = belong[l],y = belong[r],ans = 0,t1,t2;
memset(vis,0,sizeof(vis));
if(x == y || x+1 == y)
{
for(int i = l;i <= r;i++)
if(!vis[a[i]])
//如果a[i]这个数字没有查询过
{
if(!(sigma(l,r,a[i])&1))
//如果a[i]在[l,r]之间出现的次数为偶数次
ans++;
vis[a[i]] = 1;
}
}
else
{
x++;
y--;
ans = f[x][y];
for(int i = l;i <= L[x]-1;i++)
if(!vis[a[i]])
//如果数字a[i]没有查询过
{
t2 = sigma(l,L[x]-1,a[i])+sigma(R[y]+1,r,a[i]);
t1 = sigma(L[x],R[y],a[i]);
if(!(t2&1) && t2 != 0 && t1 == 0)
//如果t2为非零的偶数,且在大块中没有找到
ans++;
if((t2&1) && (t1&1))
//如果t1,t2都为奇数,也就是说大块小块找到的都是奇数次，则并起来为偶数次
ans++;
if((t2&1) && !(t1&1) && t1 != 0)
//如果t2为奇数,t1为非0的偶数(在大块中出现了)
//但在小块中出现次数为奇数，则整体为奇数
ans--;
vis[a[i]] = 1;
}
for(int i = R[y]+1;i <= r;i++)
if(!vis[a[i]])
{
t2 = sigma(l,L[x]-1,a[i])+sigma(R[y]+1,r,a[i]);
t1 = sigma(L[x],R[y],a[i]);
if(!(t2&1) && t2 != 0 && t1 == 0) ans++;
if((t2&1) && (t1&1)) ans++;
if((t2&1) && !(t1&1) && t1 != 0) ans--;
vis[a[i]] = 1;
}
}
return ans;
}
int main()
{
int c,m,l,r;
scanf("%d%d%d",&n,&c,&m);
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
pos[a[i]].push_back(i);
}
int block=sqrt((double)n/log((double)n)*log(2));
if(n % block)
bs = n/block+1;
else
bs = n/block;
for(int i = 1;i <= n;i++)
belong[i] = (i-1)/block+1;
for(int i = 1;i <= bs;i++)
{
L[i] = (i-1)*block+1; //第i块左边界
R[i] = i*block;//第i块右边界
}
R[bs] = n;
pre();
int ans = 0;
while(m--)
{
scanf("%d%d",&l,&r);
l = (l+ans) % n + 1;
r = (r+ans) % n + 1;
if (l > r)
swap(l,r);
ans = query(l,r);
printf("%d\n",ans);
}
return 0;
}
原文：https://www.cnblogs.com/cutemush/p/12795673.html