题意：求区间出现偶数次的数的异或值。序列长度是1000000，操作是1000000.
题解：求出区间不同的数的异或值，然后区间异或值^不同的数的异或值 = 出现偶数次的数的异或值。不同数的异或值用离线的方式处理，用树状数组维护。
#include<bits/stdc++.h> using namespace std; class FenWick{ private: int n; vector<int> d; public: void init(int n){ this->n = n+1; d = vector<int>(this->n,0); } int lowbit(int x){ return x&-x; } void add(int p,int x){ while(p<n){ d[p]+=x; p+=lowbit(p); } } void xor_add(int p,int x){ // cout<<p<<"----"<<x<<endl; while(p<n){ d[p]^=x; p+=lowbit(p); } } int sum(int p){ int ret = 0; while(p){ ret+=d[p]; p-=lowbit(p); } return ret; } int xor_sum(int p){ int ret = 0; while(p){ ret^=d[p]; p-=lowbit(p); } return ret; } }; struct Node{ int x,y,id; int ret; Node(int x,int y,int id):x(x),y(y),id(id){} Node(){} }; bool cmpY(const Node &a,const Node &b){ return a.y<b.y; } bool cmpID(const Node &a,const Node &b){ return a.id<b.id; } int main(){ ios_base::sync_with_stdio(false); int n; while(scanf(" %d",&n)==1){ vector<int> a(n+1,0); for(int i=1;i<=n;i++){ //cin>>a[i]; scanf(" %d",&a[i]); } int q; //cin>>q; scanf(" %d",&q); vector<Node> pd(q); for(int i=0;i<q;i++){ //cin>>pd[i].x>>pd[i].y; scanf(" %d %d",&pd[i].x,&pd[i].y); pd[i].id=i; } sort(pd.begin(),pd.end(),cmpY); FenWick fw; fw.init(n); map<int,int> kk; for(int i=1,j=0;i<=n&&j<(int)pd.size();i++){ if(kk.count(a[i])){ fw.xor_add(kk[a[i]],a[i]); } kk[a[i]]=i; fw.xor_add(i,a[i]); a[i]^=a[i-1]; //计算出不同数的xor 全部数的xor 异或它就是答案了 // cout<<"XOR:"<<fw.xor_sum(i)<<endl; while(j<(int)pd.size()&&pd[j].y==i){ // cout<<pd[j].x<<","<<pd[j].y<<endl; // cout<<a[i]<<","<<a[pd[j].x-1]<<","<<fw.xor_sum(i)<<","<<fw.xor_sum(pd[j].x-1)<<endl; pd[j].ret = a[i]^a[pd[j].x-1]^fw.xor_sum(i)^fw.xor_sum(pd[j].x-1); //cout<<(12^0^12^0)<<endl; //cout<<(a[i]^a[pd[j].x-1]^fw.xor_sum(i)^fw.xor_sum(pd[j].x-1))<<endl; j++; } } sort(pd.begin(),pd.end(),cmpID); for(int i=0;i<q;i++){ //cout<<pd[i].ret<<endl; printf("%d\n",pd[i].ret); } } return 0; }
