CF703D Mishka and Interesting sum |莫队

给你n( 1<=n<=1000000)个数,以及m(1<=m<=1000000)个询问,每个询问包括l和r，问你在这n个数中，区间l~r，出现偶数个数的数的亦或和

莫队模板，还要一点卡常

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e6+10;
#define int long long
struct node{
	int l,r,id;
}e[N];
int n,m;
int a[N],b[N];
int belong[N];
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;
}
bool cmp(node a,node b){
	return (belong[a.l]^belong[b.l]) ? a.l<b.l : belong[a.l]&1 ? a.r<b.r:a.r>b.r;
}
int cnt[N],op;
inline void add(int x){
	cnt[a[x]]++;
	if(cnt[a[x]]-1)op^=b[a[x]];
}
inline void del(int x){
	cnt[a[x]]--;
	if(cnt[a[x]])op^=b[a[x]];
}
int ans[N];
signed main(){
	read(n);
	int size=pow(n,1.0/2.0);
	int num=ceil((double)n/size);
	for(int i=1;i<=num;i++)
	for(int j=(i-1)*size+1;j<=i*size;j++)
	belong[j]=i;
	for(int i=1;i<=n;i++){
		read(a[i]);b[i]=a[i];
	}
	sort(b+1,b+1+n);
	int len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)
	a[i]=lower_bound(b+1,b+1+len,a[i])-b;
	read(m);
	for(int i=1;i<=m;i++){
		read(e[i].l);
		read(e[i].r);
		e[i].id=i;
	}
	sort(e+1,e+1+m,cmp);
	
	int l=e[1].l,r=e[1].r;
	for(int i=l;i<=r;i++)add(i);
	
	for(int i=1;i<=m;i++){
		while(l<e[i].l)del(l++);
		while(l>e[i].l)add(--l);
		while(r<e[i].r)add(++r);
		while(r>e[i].r)del(r--);
		ans[e[i].id]=op;
	}
	for(int i=1;i<=m;i++)printf("%lld
",ans[i]);
}