Discription
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, ..., ajis 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.
Example
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
Note
In the first sample the suitable pairs of i and j for the first query are: (1, 2), (1, 4), (1, 5), (2, 3), (3, 6), (5, 6), (6, 6). Not a single of these pairs is suitable for the second query.
In the second sample xor equals 1 for all subarrays of an odd length.
一个比较显然的做法是找出所有点对之后上主席树，然后我就RE了hhh，这说明点对还是有点多的，，，
先放一个我RE的代码，，，改完了再贴正解
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #include<set> #include<queue> #include<vector> #define ll long long #define pb push_back #define maxn 100005 using namespace std; //g[i]是前缀异或和==i的位置链表 vector<int> g[maxn*10]; //point[i]以i为右端点的满足条件的对的左端点集合 vector<int> point[maxn]; int n,k,now,pre,sz; int pos,m,le,ri; struct node{ int s,lc,rc; }nil[maxn*177]; int rot[maxn],cnt=0; int update(int u,int l,int r){ int ret=++cnt; nil[ret]=nil[u]; nil[ret].s++; if(l==r) return ret; int mid=l+r>>1; if(le<=mid) nil[ret].lc=update(nil[ret].lc,l,mid); else nil[ret].rc=update(nil[ret].rc,mid+1,r); return ret; } int query(int u,int l,int r){ if(l>=le&&r<=ri) return nil[u].s; int an=0,mid=l+r>>1; if(le<=mid) an=query(nil[u].lc,l,mid); if(ri>mid) an+=query(nil[u].rc,mid+1,r); return an; } inline void prework(){ nil->s=0; for(int i=1;i<=n;i++){ rot[i]=rot[i-1]; for(int j=point[i].size()-1;j>=0;j--){ le=point[i][j]; rot[i]=update(rot[i],1,n); } } } int main(){ scanf("%d%d%d",&n,&m,&k); pre=0,g[0].pb(0); for(int i=1;i<=n;i++){ scanf("%d",&now); pre^=now,now=k^pre; sz=g[now].size(); for(int j=0;j<sz;j++){ pos=g[now][j]; point[i].pb(pos+1); } g[pre].pb(i); } prework(); while(m--){ scanf("%d%d",&le,&ri); printf("%d ",query(rot[ri],1,n)); } return 0; }
第二遍莫队。。。然而又RE了。。。。
(估计是点对太多不能直接存hhhhh)
等我再改改
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #include<set> #include<queue> #include<vector> #define ll long long #define pb push_back #define maxn 100005 using namespace std; //g[i]是前缀异或和==i的位置链表 vector<int> g[maxn*10]; //point[i]以i为右端点的满足条件的对的左端点集合 vector<int> point[maxn]; vector<int> rig[maxn]; int n,k,now,pre,sz; int pos,m,le,ri,tot; /* struct node{ int s,lc,rc; }nil[maxn*177]; int rot[maxn],cnt=0; int update(int u,int l,int r){ int ret=++cnt; nil[ret]=nil[u]; nil[ret].s++; if(l==r) return ret; int mid=l+r>>1; if(le<=mid) nil[ret].lc=update(nil[ret].lc,l,mid); else nil[ret].rc=update(nil[ret].rc,mid+1,r); return ret; } int query(int u,int l,int r){ if(l>=le&&r<=ri) return nil[u].s; int an=0,mid=l+r>>1; if(le<=mid) an=query(nil[u].lc,l,mid); if(ri>mid) an+=query(nil[u].rc,mid+1,r); return an; } inline void prework(){ nil->s=0; for(int i=1;i<=n;i++){ rot[i]=rot[i-1]; for(int j=point[i].size()-1;j>=0;j--){ le=point[i][j]; rot[i]=update(rot[i],1,n); } } } */ struct node{ int l,r,bl,num; bool operator <(const node& u)const{ return bl==u.bl?((bl&1)?r<u.r:r>u.r):bl<u.bl; } }q[maxn]; int ans[maxn]; inline void adl(int x){ tot+=upper_bound(rig[x].begin(),rig[x].end(),ri)-rig[x].begin(); } inline void del(int x){ tot-=upper_bound(rig[x].begin(),rig[x].end(),ri)-rig[x].begin(); } inline void adr(int x){ tot+=point[x].size()-(lower_bound(point[x].begin(),point[x].end(),le)-point[x].begin()); } inline void der(int x){ tot-=point[x].size()-(lower_bound(point[x].begin(),point[x].end(),le)-point[x].begin()); } int main(){ scanf("%d%d%d",&n,&m,&k); pre=0,g[0].pb(0); for(int i=1;i<=n;i++){ scanf("%d",&now); pre^=now,now=k^pre; sz=g[now].size(); for(int j=0;j<sz;j++){ pos=g[now][j]; //枚举顺序保证了两个链表的元素都是升序的 point[i].pb(pos+1); rig[pos+1].pb(i); } g[pre].pb(i); } sz=sqrt(n); for(int i=1;i<=m;i++){ scanf("%d%d",&q[i].l,&q[i].r); q[i].bl=(q[i].l-1)/sz+1; q[i].num=i; } sort(q+1,q+m+1); le=1,ri=0; for(int i=1;i<=m;i++){ while(le<q[i].l) del(le),le++; while(le>q[i].l) le--,adl(le); while(ri<q[i].r) ri++,adr(ri); while(ri>q[i].r) der(ri),ri--; ans[q[i].num]=tot; } for(int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }
虽然现在A了但是首先声明一下之前让我RE的可能不是炸数组而是xor出的数>=1000000，，，，，
现在写了一个正确的莫队。。。。
其实不用计点对，现算也来得及(二分)
Accepted
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #include<set> #include<queue> #include<vector> #define ll long long #define pb push_back #define maxn 100005 using namespace std; //g[i]是前缀异或和==i的位置链表 vector<int> g[maxn*33]; int n,k,now,pre,sz,a[maxn]; int pos,m,le,ri; ll tot=0; struct node{ int l,r,bl,num; bool operator <(const node& u)const{ return bl==u.bl?((bl&1)?r<u.r:r>u.r):bl<u.bl; } }q[maxn]; ll ans[maxn]; inline void adl(int x){ int to=k^a[x-1]; if(!g[to].size()) return; tot+=(ll)(upper_bound(g[to].begin(),g[to].end(),ri)-lower_bound(g[to].begin(),g[to].end(),x)); } inline void del(int x){ //因为对于本题插入和删除带来的数值影响相同， //所以不用反着操作 int to=k^a[x-1]; if(!g[to].size()) return; tot-=(ll)(upper_bound(g[to].begin(),g[to].end(),ri)-lower_bound(g[to].begin(),g[to].end(),x)); } inline void adr(int x){ int to=k^a[x]; if(!g[to].size()) return; tot+=(ll)(lower_bound(g[to].begin(),g[to].end(),x)-lower_bound(g[to].begin(),g[to].end(),le-1)); } inline void der(int x){ int to=k^a[x]; if(!g[to].size()) return; tot-=(ll)(lower_bound(g[to].begin(),g[to].end(),x)-lower_bound(g[to].begin(),g[to].end(),le-1)); } int main(){ scanf("%d%d%d",&n,&m,&k); g[0].pb(0); for(int i=1;i<=n;i++){ scanf("%d",a+i); a[i]^=a[i-1]; g[a[i]].pb(i); } sz=sqrt(n); for(int i=1;i<=m;i++){ scanf("%d%d",&q[i].l,&q[i].r); q[i].bl=(q[i].l-1)/sz+1; q[i].num=i; } sort(q+1,q+m+1); le=1,ri=0; for(int i=1;i<=m;i++){ while(le<q[i].l) del(le),le++; while(le>q[i].l) le--,adl(le); while(ri<q[i].r) ri++,adr(ri); while(ri>q[i].r) der(ri),ri--; ans[q[i].num]=tot; } for(int i=1;i<=m;i++) printf("%lld ",ans[i]); return 0; }