E. XOR and Favorite Number
思路：
区间[l,r]的异或和是pre[r]^pre[l-1]，如果满足区间内的异或和=k就是pre[r]^pre[l-1] = k;
可以写成pre[l-1]^k = pre[r]，或者pre[r]^k = pre[l-1]。
所以用数组num记录前缀和出现的次数，
如果是增加添加这个节点，先添加，再更新，
如果是删除这个节点，先更新，再删除（考虑如果k = 0,a[x]^k = a[x],因为a[x]已经被删除了，所以计算结果时不用考虑a[x],
但是没有提前删除这个节点，使结果变小，所以要先更新节点，然后再删除）。
代码：（注意ll，数据范围）
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn = 3e6+10; typedef long long LL; int n,m,pre[maxn]={0},Ki[maxn]={0},l = 1,r = 0; LL ans = 0,k,Ans[maxn]={0},num[maxn]={0}; struct Node{ int id,l,r; }cur[maxn]; bool cmp(Node a,Node b){ if(Ki[a.l]==Ki[b.l]) return a.r<b.r; return a.l<b.l; } void Add(int x,int d){ if(d>0){ ans += num[pre[x]^k]; num[pre[x]]++; }else{ num[pre[x]]--; ans -= num[pre[x]^k]; } } int main(void){ scanf("%d%d%lld",&n,&m,&k); int unit = (int)sqrt(n);num[0] = 1; for(int i=1;i<=n;i++){ LL x;scanf("%lld",&x);pre[i] = pre[i-1]^x;Ki[i] = i/unit+1; } for(int i=1;i<=m;i++){ scanf("%d%d",&cur[i].l,&cur[i].r);cur[i].id = i; } sort(cur+1,cur+1+m,cmp); for(int i=1;i<=m;i++){ while(l<cur[i].l){ Add(l-1,-1);l++; } while(l>cur[i].l){ Add(l-2,1);l--; } while(r>cur[i].r){ Add(r,-1);r--; } while(r<cur[i].r){ Add(r+1,1);r++; } Ans[cur[i].id] = ans; } for(int i=1;i<=m;i++) printf("%lld\n",Ans[i]); return 0; }
