題目鏈接：點擊查看

題目大意：給出一個由n個數組成的數列，現在給出m組詢問，每次詢問包含一個l和一個r，要求回答在閉區間[l,r]中有多少組(i,j)滿足[i,j]閉區間內的所有數的異或和等于k

題目分析：一看數據范圍暴力肯定是不能做的，而且m給的也很大，還是離線操作，所以我們可以考慮用莫隊來處理這個問題，二話不說就直接把板子貼過來了，現在的問題就是編寫一下add和del這兩個函數了

因為要求區間異或和，我們不妨在輸入的時候就順便把異或和維護一下，要求[l,r]之間的異或和，答案就是a[r]^a[l-1]，注意一下這里的l-1，我一開始沒想那么多，當成l做的，調試的時候都快自閉了。。

下面我們設計add和del函數，當我們要加入或刪除pos位置數的時候，只需要找一下當前區間內有多少個值為pos^k的數即可，因為這些數都可以滿足上面提到的式子，從而滿足區間異或和的結果等于k，這樣我們就好做了，只需要維護一個cnt記錄一下每個值出現的次數即可，因為k的上限給到了1e6，根據異或的性質，答案肯定不可能超過二進制中的最高位，所以我們直接開一個2e6的cnt數組維護即可，這里需要注意一下，當前加入或刪除的數，當k=0的時候，順序對答案是有貢獻的，所以在add函數里我們需要先計算貢獻再將其自增，在del函數里我們需要先將其自減再計算貢獻

然后就是cnt數組了，我一開始用的無序map，因為懶得算那么多東西，但最后發現無序map雖然時間復雜度幾乎都是O(1)級別的，但對于這個題目還是跑了1.5秒，換成數組之后直接下降到了300毫秒，這個時間開銷還是比較客觀的，所以以后能用數組就用數組吧，盡量別用stl

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int size,n,m,k,a[N];LL ans[N];LL cnt[N*20];struct query {int l,r,id;bool operator<(const query& a)const{if(l/size!=a.l/size)return l<a.l;else if((l/size)&1)return r<a.r;elsereturn r>a.r;} }q[N];LL add(int pos) {LL ans=cnt[a[pos]^k];//先計算貢獻cnt[a[pos]]++;//再自增return ans; }LL del(int pos) {cnt[a[pos]]--;//先自減LL ans=cnt[a[pos]^k];//再計算貢獻return -ans; }void solve() {int l=1,r=0;LL sum=0;for(int i=1;i<=m;i++){int ql=q[i].l;int qr=q[i].r;while(l<ql)sum+=del(l++);while(l>ql)sum+=add(--l);while(r<qr)sum+=add(++r);while(r>qr)sum+=del(r--);ans[q[i].id]=sum;} }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%d%d%d",&n,&m,&k);size=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",a+i);a[i]^=a[i-1];}for(int i=1;i<=m;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].l--;//注意這里，讓l自減，達到區間變為[l-1,r]的目的q[i].id=i;}sort(q+1,q+1+m);solve();for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);return 0; }

?

總結

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

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