↵
E. XOR and Favorite Number↵
time limit per test4 seconds↵
memory limit per test256 megabytes↵
inputstandard input↵
outputstandard output↵
Bob has a favorite number k and ai of length n. Now he asks you to answer m queries. Each query is given by a pair li and ri and asks you to count the number of pairs of integers i and j, such that l ≤ i ≤ j ≤ r and the xor of the numbers ai, ai + 1, ..., aj is equal to k.↵
↵
Input↵
The first line of the input contains integers n, m and k (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 1 000 000) — the length of the array, the number of queries and Bob's favorite number respectively.↵
↵
The second line contains n integers ai (0 ≤ ai ≤ 1 000 000) — Bob's array.↵
↵
Then m lines follow. The i-th line contains integers li and ri (1 ≤ li ≤ ri ≤ n) — the parameters of the i-th query.↵
↵
Output↵
Print m lines, answer the queries in the order they appear in the input.↵
↵
Sample test(s)↵
input↵
6 2 3↵
1 2 1 1 0 3↵
1 6↵
3 5↵
output↵
7↵
0↵
input↵
5 3 1↵
1 1 1 1 1↵
1 5↵
2 4↵
1 3↵
output↵
9↵
4↵
4↵
↵
。。好题，我一开始觉得一定是按分块分的可持久化字典树，具体做法呢就是先利用莫队算法，然后将区间内的所有a[i]都加入字典树，然后对于每个节点我们都有对应能异或得k的所有对应节点，然后我们边修改l和r边修改ans。↵
然后因为位数在20左右，所以非常完美，不会爆炸。↵
↵
以上都是yy，其实这题只要用一个sum【i】数组存一个前缀异或和，sum[r]^sum[l-1]就是a[l]到a[r]的异或和了，这样我们每加入一个sum[i]都有对应的op[sum[i]]，这样我们再记录一个cnt[i]代表目前a[j]值为i的j的个数↵
这样ans就能+=cnt[i]*cnt[op[i]]，此外，如果k=0，那么便有l=r的情况出现，然而k=0我们只需要特殊处理即可，此题还需要注意longlong，反正我把全部int改成long long了。↵
代码：↵
↵
↵
~~~~~↵
#include<iostream>↵
#include<cstdio>↵
#include<cstring>↵
#include<cmath>↵
#include<string>↵
#include<algorithm>↵
#define ll long long↵
struct wow{↵
ll id,ans,l,r;↵
}ans[1000005];↵
ll l,r,mx,a[1000005],block,n,m,k,now,cnt[2000005],sum[1000005],op[2000005],pos[1000005];↵
bool cmp1(wow q,wow w){↵
if (pos[q.l]==pos[w.l]) return q.r<w.r;↵
return pos[q.l]<pos[w.l];↵
}↵
bool cmp2(wow q,wow w){↵
return q.id<w.id;↵
}↵
void updata(ll x,ll v){↵
if (k!=0)↵
now-=cnt[sum[x]]*cnt[op[sum[x]]];↵
else↵
now-=((cnt[sum[x]]-1)*(cnt[sum[x]]))/2;↵
cnt[sum[x]]+=v;↵
if (k!=0)↵
now+=cnt[sum[x]]*cnt[op[sum[x]]];↵
else↵
now+=((cnt[sum[x]]-1)*(cnt[sum[x]]))/2;↵
}↵
int main(){↵
//freopen("tx.in","r",stdin);↵
scanf("%I64d%I64d%I64d",&n,&m,&k);↵
block=sqrt(n);↵
for (int i=1;i<=n;i++)↵
pos[i]=i/block;↵
for (int i=1;i<=n;i++)↵
scanf("%I64d",&a[i]);↵
for (int i=1;i<=n;i++) ↵
sum[i]=sum[i-1]^a[i],mx=std::max(mx,sum[i]);↵
for (int i=0;i<=mx;i++)↵
op[i]=i^k;↵
for (int i=1;i<=m;i++){↵
scanf("%I64d%I64d",&ans[i].l,&ans[i].r);↵
ans[i].l--;↵
ans[i].id=i;↵
ans[i].ans=0;↵
} ↵
std::sort(ans+1,ans+1+m,cmp1);↵
l=ans[1].l;r=ans[1].l;cnt[sum[l]]++;now=0;↵
for (int i=1;i<=m;i++){↵
if (l<ans[i].l){↵
for (int j=l;j<ans[i].l;j++)↵
updata(j,-1);↵
}↵
else↵
if (l>ans[i].l){↵
for (int j=l-1;j>=ans[i].l;j--)↵
updata(j,1);↵
}↵
l=ans[i].l;↵
if (r<ans[i].r){↵
for (int j=r+1;j<=ans[i].r;j++)↵
updata(j,1);↵
}↵
else↵
if (r>ans[i].r){↵
for (int j=r;j>ans[i].r;j--)↵
updata(j,-1);↵
}↵
r=ans[i].r;↵
ans[i].ans=now; ↵
}↵
std::sort(ans+1,ans+1+m,cmp2);↵
for (int i=1;i<=m;i++)↵
printf("%I64d\n",ans[i].ans);↵
} ↵
~~~~~↵
E. XOR and Favorite Number↵
time limit per test4 seconds↵
memory limit per test256 megabytes↵
inputstandard input↵
outputstandard output↵
Bob has a favorite number k and ai of length n. Now he asks you to answer m queries. Each query is given by a pair li and ri and asks you to count the number of pairs of integers i and j, such that l ≤ i ≤ j ≤ r and the xor of the numbers ai, ai + 1, ..., aj is equal to k.↵
↵
Input↵
The first line of the input contains integers n, m and k (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 1 000 000) — the length of the array, the number of queries and Bob's favorite number respectively.↵
↵
The second line contains n integers ai (0 ≤ ai ≤ 1 000 000) — Bob's array.↵
↵
Then m lines follow. The i-th line contains integers li and ri (1 ≤ li ≤ ri ≤ n) — the parameters of the i-th query.↵
↵
Output↵
Print m lines, answer the queries in the order they appear in the input.↵
↵
Sample test(s)↵
input↵
6 2 3↵
1 2 1 1 0 3↵
1 6↵
3 5↵
output↵
7↵
0↵
input↵
5 3 1↵
1 1 1 1 1↵
1 5↵
2 4↵
1 3↵
output↵
9↵
4↵
4↵
↵
。。好题，我一开始觉得一定是按分块分的可持久化字典树，具体做法呢就是先利用莫队算法，然后将区间内的所有a[i]都加入字典树，然后对于每个节点我们都有对应能异或得k的所有对应节点，然后我们边修改l和r边修改ans。↵
然后因为位数在20左右，所以非常完美，不会爆炸。↵
↵
以上都是yy，其实这题只要用一个sum【i】数组存一个前缀异或和，sum[r]^sum[l-1]就是a[l]到a[r]的异或和了，这样我们每加入一个sum[i]都有对应的op[sum[i]]，这样我们再记录一个cnt[i]代表目前a[j]值为i的j的个数↵
这样ans就能+=cnt[i]*cnt[op[i]]，此外，如果k=0，那么便有l=r的情况出现，然而k=0我们只需要特殊处理即可，此题还需要注意longlong，反正我把全部int改成long long了。↵
代码：↵
↵
↵
~~~~~↵
#include<iostream>↵
#include<cstdio>↵
#include<cstring>↵
#include<cmath>↵
#include<string>↵
#include<algorithm>↵
#define ll long long↵
struct wow{↵
ll id,ans,l,r;↵
}ans[1000005];↵
ll l,r,mx,a[1000005],block,n,m,k,now,cnt[2000005],sum[1000005],op[2000005],pos[1000005];↵
bool cmp1(wow q,wow w){↵
if (pos[q.l]==pos[w.l]) return q.r<w.r;↵
return pos[q.l]<pos[w.l];↵
}↵
bool cmp2(wow q,wow w){↵
return q.id<w.id;↵
}↵
void updata(ll x,ll v){↵
if (k!=0)↵
now-=cnt[sum[x]]*cnt[op[sum[x]]];↵
else↵
now-=((cnt[sum[x]]-1)*(cnt[sum[x]]))/2;↵
cnt[sum[x]]+=v;↵
if (k!=0)↵
now+=cnt[sum[x]]*cnt[op[sum[x]]];↵
else↵
now+=((cnt[sum[x]]-1)*(cnt[sum[x]]))/2;↵
}↵
int main(){↵
//freopen("tx.in","r",stdin);↵
scanf("%I64d%I64d%I64d",&n,&m,&k);↵
block=sqrt(n);↵
for (int i=1;i<=n;i++)↵
pos[i]=i/block;↵
for (int i=1;i<=n;i++)↵
scanf("%I64d",&a[i]);↵
for (int i=1;i<=n;i++) ↵
sum[i]=sum[i-1]^a[i],mx=std::max(mx,sum[i]);↵
for (int i=0;i<=mx;i++)↵
op[i]=i^k;↵
for (int i=1;i<=m;i++){↵
scanf("%I64d%I64d",&ans[i].l,&ans[i].r);↵
ans[i].l--;↵
ans[i].id=i;↵
ans[i].ans=0;↵
} ↵
std::sort(ans+1,ans+1+m,cmp1);↵
l=ans[1].l;r=ans[1].l;cnt[sum[l]]++;now=0;↵
for (int i=1;i<=m;i++){↵
if (l<ans[i].l){↵
for (int j=l;j<ans[i].l;j++)↵
updata(j,-1);↵
}↵
else↵
if (l>ans[i].l){↵
for (int j=l-1;j>=ans[i].l;j--)↵
updata(j,1);↵
}↵
l=ans[i].l;↵
if (r<ans[i].r){↵
for (int j=r+1;j<=ans[i].r;j++)↵
updata(j,1);↵
}↵
else↵
if (r>ans[i].r){↵
for (int j=r;j>ans[i].r;j--)↵
updata(j,-1);↵
}↵
r=ans[i].r;↵
ans[i].ans=now; ↵
}↵
std::sort(ans+1,ans+1+m,cmp2);↵
for (int i=1;i<=m;i++)↵
printf("%I64d\n",ans[i].ans);↵
} ↵
~~~~~↵
