<span>codeforces703D Mishka and Interesting sum（区间偶数异或）</span>
题意：
给你一个序列，q个询问l,r
要求出l到r区间内出现偶数次的数的异或值
思路：
预处理异或前缀sum
将询问按r放入vector，存的pair<l,i>
树状数组部分有点同于求区间数的种数。
last记录每个数前一次出现的位置。
走到i时，如果a[i]出现过，那么把他上次出现的位置异或掉，再在i位置上异或上a[i]。
然后对所有以i结尾的讯问区间进行操作，这里就是异或计算了。
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <string> #include <cmath> #include <stdlib.h> #define inf 0x3f3f3f3f #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define mkp make_pair template<class T>inline void rd(T &x){char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-'0';c=getchar();}} #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int mod=1e9+7; const int N=1e6+10; int a[N],sum[N],c[N],ans[N],n,q,l,r; vector<pair<int,int> >eg[N]; map<int,int>last; int lowbit(int x) { return x&(-x); } int add(int i,int val) { for(;i<=n;i+=lowbit(i)) c[i]^=val; } int summ(int i) { int ret=0; for(;i>0;i-=lowbit(i)) ret^=c[i]; return ret; } int main() { rd(n); rep(i,1,n) rd(a[i]),sum[i]=sum[i-1]^a[i]; rd(q); rep(i,1,q) { rd(l),rd(r); eg[r].pb(mkp(l,i)); } int cnt=0; rep(i,1,n) { if(last.count(a[i])) add(last[a[i]],a[i]); add(i,a[i]); last[a[i]]=i; for(int j=0;j<eg[i].size();j++) { int tmp=sum[i]^sum[eg[i][j].first-1]; tmp^=(summ(i)^summ(eg[i][j].first-1)); ans[eg[i][j].second]=tmp; cnt++; } if(cnt==q) break; } rep(i,1,q) ou(ans[i]); return 0; }
长安汽车成长空间 27人发布