题解 CF703D 【Mishka and Interesting sum】
ChthollyTree
2019-03-29 17:56:14
看到题目，区间数字出现偶数个数的数的xor
第一反应是莫队对吧
统计一下区间里每个数字出现几次就好了
裸的莫队模板？
但是一看数据范围 n <= $10^6$
好吧
但是我们可以卡常
方法：
1.使用读入优化
2.分奇偶排序
3.调节块的大小
然后就可以根号过百万了
```
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000005
struct wen {
int l,r,i;
}c[MAXN];
int a[MAXN];
int d[MAXN];
int p[MAXN];
int pos[MAXN];
int n,m;
namespace lsh
{
struct aa
{
int a,i,c;
}p[MAXN];
bool cmp(aa a,aa b) {
return a.a < b.a;
}
void main()
{
for(int i = 1; i <= n; i ++) {
p[i].i = i;
p[i].a = a[i];
}
sort(p+1,p+n+1,cmp);
for(int i = 1; i <= n; i ++)
if(p[i].a == p[i-1].a) d[p[i].i] = d[p[i-1].i];
else d[p[i].i] = d[p[i-1].i]+1;
}
}
bool cmp(wen a,wen b){
return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:pos[a.l]&1?a.r<b.r:a.r>b.r;
}
inline void read(int &x) {
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
void rd()
{
read(n);
for(int i = 1; i <= n; i ++)
read(a[i]);
read(m);
for(int i = 1; i <= m; i ++) {
read(c[i].l);
read(c[i].r);
c[i].i = i;
}
int nn = n/sqrt(m*0.9);
for(int i = 1; i <= n; i ++)
pos[i] = i/nn;
lsh::main();
sort(c+1,c+m+1,cmp);
}
int an;
int ans[MAXN];
void jia(int x)
{
++ p[d[x]];
if(p[d[x]] != 1) an ^= a[x];
}
void jian(int x)
{
-- p[d[x]];
if(p[d[x]] != 0) an ^= a[x];
}
int main()
{
rd();
int l = 1,r = 0;
for(int i = 1; i <= m; i ++)
{
while(r < c[i].r)
{
r ++;
jia(r);
}
while(l > c[i].l)
{
-- l;
jia(l);
}
while(r > c[i].r) {
jian(r);
r --;
}
while(l < c[i].l) {
jian(l);
l ++;
}
ans[c[i].i] = an;
}
for(int i = 1; i <= m; i ++)
printf("%d\n",ans[i]);
return 0;
}
```