可以做围棋习题的网站,廉政网站建设经验交流,网页界面分析及设计布局,天津网站制作首页在线咨询正题
题目链接:https://www.luogu.com.cn/problem/P3760 题目大意
给出nnn个数字的一个序列aaa#xff0c;求它所有区间和的异或和 n≤105,∑ai≤106n\leq 10^5,\sum a_i\leq 10^6n≤105,∑ai≤106 解题思路
开始写了个前缀和FFTFFTFFT发现要卡常然后就换了个方法。
每一…正题
题目链接:https://www.luogu.com.cn/problem/P3760 题目大意
给出nnn个数字的一个序列aaa求它所有区间和的异或和
n≤105,∑ai≤106n\leq 10^5,\sum a_i\leq 10^6n≤105,∑ai≤106 解题思路
开始写了个前缀和FFTFFTFFT发现要卡常然后就换了个方法。
每一个位分开考虑现在要求有多少个区间和的第kkk位是111。
设sumsumsum为区间和那么为了方便计算我们要把andandand操作转换一下。就有sum%2k1∈[2k,2k1)sum\% 2^{k1}\in[2^{k},2^{k1})sum%2k1∈[2k,2k1)。
看起来好像更复杂了其实没有因为2k2^k2k我们可以直接枚举那么对于模2k12^{k1}2k1次方意义下在[2k,2k1)[2^{k},2^{k1})[2k,2k1)范围内的区间和就符合要求。
这个就是树状数组的活了
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n)反正是logloglog∑ai\sum a_i∑ai算和nnn同级得了 code
#includecstdio
#includecstring
#includealgorithm
#define lowbit(x) (x-x)
using namespace std;
const int N120;
int n,a[N],t[N],ans,lim;
void Change(int x,int val){x;while(xlim){t[x]val;xlowbit(x);}return;
}
int Ask(int x){int ans0;x;while(x){anst[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 i1;in;i){scanf(%d,a[i]);a[i]a[i-1];}for(int lg1;lg20;lg){lim(1lg);int klim1,tmp0;Change(0,1);for(int i1;in;i){ int wa[i]%lim;if(wk)tmpQuery(w1,lim-1)Query(0,(wk)%lim);else tmpQuery(w1,wk);Change(w,1);tmp%2;}for(int i1;in;i)Change(a[i]%lim,-1);if(tmp1)ans|k;Change(0,-1);}printf(%d\n,ans);
}
