强制在线，不能用莫队、树状数组等优雅算法，考虑暴力分块。
设分块后，f[i] [j] 表示第i块到第j块的答案。
于是，对于每次询问，设p为l所在块的编号，q为r所在块的编号，先查询l到r之间整块的答案，即f[p] [q]。
之后对于两边的不完整的块，暴力扫每个数，记录出现次数，与这个数在第p块和第q块之间出现的次数比较
于是，问题关键在于如何快速求出某个数在任意两块间的出现次数。
记分块的数量为T，每块的长度len = n / T。序列长度n、询问次数m同阶。
解法一：
与 洛谷P4168 [Violet]蒲公英 类似，对每种数开一个vector，存下这个数在原序列中出现的位置，查询某个数在[L,R]出现次数，只需二分查找<=R的最大下标和>=L的最小下标作差+1.
如 1 2 2 1 2 3 2 这组数，查询2在[3，6]之间出现的次数。vector[2]={2,3,5,7}，即2在原序列中出现的位置。二分查找<=6的最大数为5，在vector中下标为2（vector下标从0开始），之后再二分查找>=3的最小数为3，在vector中的下标为1，两个下标作差+1 = 2，即查询结果为2。
预处理时，从每个块的起点到n进行统计，复杂度\(O(T*n)\) 。
查询时，对两边不完整块的每个数需要二分查找，每次查找为\(logn\) ，共\(n/T\) 个数。
总时间复杂度\(O(nT+m(n/T*logn))\) ，空间为\(T^2\) ,取\(T=\sqrt{n*logn}\) ，此时总复杂度\(O(n\sqrt{n*logn})\) 。
注意：
Code
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5, T = 1280;
vector<int> pos[N];
int n, c, m, len, tim, Stack[N], v[N], cnt[N], vis[N], block[N], bl[T], br[T], f[T][T];
inline void read(int &tmp) {
register char c = getchar();
for(tmp = 0; !isdigit(c); c = getchar());
for(; isdigit(c); tmp = tmp * 10 + c - 48, c = getchar());
}
void init() {
read(n);
read(c);
read(m);
len = ceil(n * 1.0 / (sqrt(n * log(n))));
for(int i = 1; i <= n; ++i) {
read(v[i]);
pos[v[i]].push_back(i);
block[i] = (i - 1) / len + 1;
}
for(int i = 1; i <= block[n]; ++i) {
bl[i] = (i - 1) * len + 1;
br[i] = i * len;
}
br[block[n]] = n;
for (int i = 1, res; i <= block[n]; ++i) {
res = 0;
for(int j = bl[i]; j <= n; ++j) cnt[v[j]] = 0;
for (int j = bl[i]; j <= n; ++j) {
++cnt[v[j]];
if ((cnt[v[j]] & 1) && (cnt[v[j]] > 1)) --res;
else if (!(cnt[v[j]] & 1)) ++res;
f[i][block[j]] = res;
}
}
}
inline int get(int x, int L, int R) {
return upper_bound(pos[x].begin(), pos[x].end(), R) - lower_bound(pos[x].begin(), pos[x].end(), L);
}
int query(int L, int R) {
int p = block[L], q = block[R], tp = 0, res = 0;
if(q - p < 2) {//同块或相邻块
for(int i = L; i <= R; ++i) {//暴力扫
if(vis[v[i]] != tim) {//第一次扫到的标记
vis[v[i]] = tim;
cnt[v[i]] = 1;
} else {
++cnt[v[i]];
if(cnt[v[i]] & 1) --res;
else ++res;
}
}
return res;
}
res = f[p + 1][q - 1];//两块间的答案
for(int i = L; i <= br[p]; ++i) {//左边角块
if(vis[v[i]] != tim) {
vis[v[i]] = tim;
cnt[v[i]] = 1;
Stack[++tp] = v[i];
} else ++cnt[v[i]];
}
for(int i = bl[q]; i <= R; ++i) {//右边角块
if(vis[v[i]] != tim) {
vis[v[i]] = tim;
cnt[v[i]] = 1;
Stack[++tp] = v[i];
} else ++cnt[v[i]];
}
while(tp) {
int t = Stack[tp--], k = get(t, bl[p + 1], br[q - 1]);
if(!k) {
if(!(cnt[t] & 1)) ++res;
} else if((k & 1) && (cnt[t] & 1)) ++res;
else if(!(k & 1) && (cnt[t] & 1)) --res;
}
return res;
}
int main() {
init();
int res = 0;
for(int i = 1, l, r; i <= m; ++i) {
++tim;
read(l);
read(r);
l = (l + res) % n + 1;
r = (r + res) % n + 1;
if(l > r) swap(l, r);
printf("%d\n", res = query(l, r));
}
return 0;
}解法二：
利用前缀和思想，设g[i] [j]表示从序列开始到第i块中，数字j的出现次数。则查询数字x在第p+1块到第q-1块的出现次数，为g[q-1] [x] - g[p] [x]。
实际写的时候，可以把g数组定义为第i块到序列末尾中数字j的出现次数，即后缀和，方便在同一个循环中处理。查询时类似于前缀和。
这样每次查询为O(1)，显然，总复杂度为\(O(n\sqrt n)\) ，空间为\((Tn)\) 。
理论复杂度比解法一快，实际上，当T取\(\sqrt n\) 时，不开O2有两个点会TLE（可能是我写的太丑了QAQ）。然鹅，T取较大值时，耗时更短，但空间会炸（要开T*n的二维数组...）
Code
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
using namespace std;
const int N = 1e5 + 5, T = 350;
int n, c, m, len, Stack[N], v[N], cnt[N], block[N], bl[T], br[T], f[T][T], g[T][N];
inline void read(int &tmp) {
register char c = getchar();
for(tmp = 0; !isdigit(c); c = getchar());
for(; isdigit(c); tmp = tmp * 10 + c - 48, c = getchar());
}
void init() {
read(n);
read(c);
read(m);
len = sqrt(n);
for(register int i = 1; i <= n; ++i) {
read(v[i]);
block[i] = (i - 1) / len + 1;
}
for(int i = 1; i <= block[n]; ++i) {
bl[i] = (i - 1) * len + 1;
br[i] = i * len;
}
br[block[n]] = n;
for (int i = 1, res; i <= block[n]; ++i) {
res = 0;
for (int j = bl[i]; j <= n; ++j) {
++g[i][v[j]];
if ((g[i][v[j]] & 1) && (g[i][v[j]] > 1)) --res;
else if (!(g[i][v[j]] & 1)) ++res;
f[i][block[j]] = res;
}
}
}
int query(int L, int R) {
int p = block[L], q = block[R];
register int res = 0, tp = 0, c, num;
if(q - p < 2) {
for(int i = L; i <= R; ++i) ++cnt[Stack[++tp] = v[i]];
while(tp) {
c = Stack[tp];
if(cnt[c]) res += (cnt[c] & 1) ^ 1;
cnt[Stack[tp--]] = 0;
}
return res;
}
res = f[p + 1][q - 1];
for(int i = L; i <= br[p]; ++i) ++cnt[Stack[++tp] = v[i]];
for(int i = bl[q]; i <= R; ++i) ++cnt[Stack[++tp] = v[i]];
while(tp) {
c = Stack[tp];
if(cnt[c]) {
num = g[p + 1][c] - g[q][c];
if((num & 1) && (cnt[c] & 1)) ++res;
else if(!(num & 1) && num && (cnt[c] & 1)) --res;
else if(!num && !(cnt[c] & 1)) ++res;
}
cnt[Stack[tp--]] = 0;
}
return res;
}
int main() {
init();
int res = 0;
for(register int i = 1, l, r; i <= m; ++i) {
read(l);
read(r);
l = (l + res) % n + 1;
r = (r + res) % n + 1;
if(l > r) swap(l, r);
printf("%d\n", res = query(l, r));
}
return 0;
}原文：https://www.cnblogs.com/yu-xing/p/10878789.html