题意
给出一个序列，求区间内出现次数为偶数的数的个数。
题解
分块。
由于“区间内出现次数为偶数”这个定语太长了，下面的题解中，我称区间内出现次数为偶数的数为“妙数”（感谢Mrsheep起了个名字）。
首先，求出中间整块部分的妙数有多少，记作ans（类似上一题BZOJ 2724，这个值可以预处理）。
接下来，我们通过处理零散部分的数，来去除错解，补上漏解。
对于每个在零散部分出现的数：
如果在零散部分它是妙数，在整块部分也是妙数，则它在整个区间仍然是妙数，并且已经包含在ans内了，我们什么都不用做。
如果在零散部分它是妙数，在整块部分出现过且不是妙数，则它在整个区间不是妙数，并且没被包含在ans内，我们也什么都不用做。
如果在零散部分它是妙数，在整块部分没出现过，则它是一个新的妙数，之前没被包含在ans内，ans++。
如果在零散部分它不是妙数，在整块部分是妙数，则这个数在整个区间不是妙数，但却被记在ans内了，需要去除，ans--。
如果在零散部分它不是妙数，在整块部分出现过且不是妙数，则它在整个区间是妙数，之前没被包含在ans内，ans++。
如果在零散部分它不是妙数，在整块部分没出现过，则它不是妙数，并且我们什么都不用做。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
#define space putchar(' ')
#define enter putchar('
')
template <class T>
void read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
template <class T>
void write(T x){
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}
const int N = 100005, B = 400;
int n, c, m, ans, l, r, a[N], res[253][253], cnt[N], sum[N][253], pos[N], lst[N], idx;
#define st(x) (((x) - 1) * B + 1)
#define ed(x) min(n, (x) * B)
#define bel(x) (((x) - 1) / B + 1)
int main(){
read(n), read(c), read(m);
for(int i = 1; i <= n; i++){
read(a[i]);
for(int j = bel(i); st(j) <= n; j++)
sum[a[i]][j]++;
}
for(int i = 1; st(i) <= n; i++){
memset(cnt, 0, sizeof(cnt));
memset(pos, 0, sizeof(pos));
int x = 0;
for(int j = st(i); j <= n; j++){
cnt[a[j]] ^= 1;
if(!cnt[a[j]]) x++; //不管算没算过，都增加了一个好数
else if(pos[a[j]]) x--; //之前算在答案里，现在变成了非好数，不该算了
pos[a[j]] = 1; //这里是标记一下这个数访问过
if(ed(bel(j)) == j) //如果j是一个块的结尾，则更新res
res[i][bel(j)] = x;
}
}
memset(pos, 0, sizeof(pos));
memset(cnt, 0, sizeof(cnt));
while(m--){
//先初始化，去除上一次询问在pos、lst、idx、cnt四个数组/变量中留下的痕迹
while(idx){
pos[lst[idx]] = 0; //pos存储的是一个数在lst中出现的位置
cnt[lst[idx]] = 0; //cnt存储的是一个数在左右两侧零散部分出现的次数
lst[idx--] = 0; //lst存储当前扫过的数
}
read(l), read(r);
l = (l + ans) % n + 1, r = (r + ans) % n + 1;
if(l > r) swap(l, r);
ans = 0;
if(bel(l) == bel(r)){
for(int i = l; i <= r; i++){
cnt[a[i]] ^= 1;
if(!pos[a[i]]) lst[++idx] = a[i], pos[a[i]] = idx;
}
for(int i = 1; i <= idx; i++)
if(!cnt[lst[i]]) ans++;
write(ans), enter;
continue;
}
for(int i = l; i <= ed(bel(l)); i++){
cnt[a[i]] ^= 1;
if(!pos[a[i]]) lst[++idx] = a[i], pos[a[i]] = idx;
}
for(int i = st(bel(r)); i <= r; i++){
cnt[a[i]] ^= 1;
if(!pos[a[i]]) lst[++idx] = a[i], pos[a[i]] = idx;
}
ans = res[bel(l) + 1][bel(r) - 1];
for(int i = 1; i <= idx; i++){
if(cnt[lst[i]]){
if((sum[lst[i]][bel(r) - 1] - sum[lst[i]][bel(l)]) & 1) ans++; //两个都是奇数次，总共偶数次
else if(sum[lst[i]][bel(r) - 1] - sum[lst[i]][bel(l)] > 0) ans--; //去掉一个错解
}
else if(sum[lst[i]][bel(r) - 1] - sum[lst[i]][bel(l)] == 0) ans++; //在大区间没出现过，加上一个解
}
write(ans), enter;
}
return 0;
}