正題

題目鏈接:https://www.luogu.com.cn/problem/P3760

---

題目大意

給出$n$個(gè)數(shù)字的一個(gè)序列$a$，求它所有區(qū)間和的異或和

$n\le 10^5,\sum a_i\le 10^6$

---

解題思路

開始寫了個(gè)前綴和$+FFT$發(fā)現(xiàn)要卡常然后就換了個(gè)方法。

每一個(gè)位分開考慮，現(xiàn)在要求有多少個(gè)區(qū)間和的第$k$位是$1$。

設(shè)$sum$為區(qū)間和，那么為了方便計(jì)算我們要把$and$操作轉(zhuǎn)換一下。就有$sum\%2^{k+1}\in [2^k,2^{k+1})$。

看起來好像更復(fù)雜了，其實(shí)沒有，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$2^k$我們可以直接枚舉，那么對(duì)于模$2^{k+1}$次方意義下在$[2^k,2^{k+1})$范圍內(nèi)的區(qū)間和就符合要求。

這個(gè)就是樹狀數(shù)組的活了

時(shí)間復(fù)雜度$O(n{\log }^{2}n)$（反正是$log$，$\sum a_i$算和$n$同級(jí)得了）

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) (x&-x) using namespace std; const int N=1<<20; int n,a[N],t[N],ans,lim; void Change(int x,int val){x++;while(x<=lim){t[x]+=val;x+=lowbit(x);}return; } int Ask(int x){int ans=0;x++;while(x){ans+=t[x];x-=lowbit(x);}return ans; } int Query(int l,int r) {return Ask(r)-Ask(l-1);} int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]+=a[i-1];}for(int lg=1;lg<=20;lg++){lim=(1<<lg);int k=lim>>1,tmp=0;Change(0,1);for(int i=1;i<=n;i++){ int w=a[i]%lim;if(w>=k)tmp+=Query(w+1,lim-1)+Query(0,(w+k)%lim);else tmp+=Query(w+1,w+k);Change(w,1);tmp%=2;}for(int i=1;i<=n;i++)Change(a[i]%lim,-1);if(tmp&1)ans|=k;Change(0,-1);}printf("%d\n",ans); }

總結(jié)

以上是生活随笔為你收集整理的P3760-[TJOI2017]异或和【树状数组】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。