Discription

Bob has a favorite number?k?and?a_i?of length?n. Now he asks you to answer?m?queries. Each query is given by a pair?l_i?and?r_i?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?a_i,?a_i?+?1,?...,?a_jis 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?a_i?(0?≤?a_i?≤?1?000?000)?— Bob's array.

Then?m?lines follow. The?i-th line contains integers?l_i?and?r_i?(1?≤?l_i?≤?r_i?≤?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\n",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\n",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\n",ans[i]);return 0; }

?

轉載于:https://www.cnblogs.com/JYYHH/p/8371381.html

總結

以上是生活随笔為你收集整理的Codeforces 617E XOR and Favorite Number的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。