首页 > 代码库 > BZOJ 4184: shallot
BZOJ 4184: shallot
Description
在某时刻加入或删除一个点,问每个时刻的集合中能异或出来的最大值是多少.
Sol
线段树+按时间分治+线性基.
把一个数字的存在时间挂在线段树的区间上,不超过 \(logn\) 个区间,所以总和不超过 \(nlogn\) 个节点信息.
然后从上往下走遍历整个线段树,每次到根节点统计一下答案,这里跟线性基有些不同,线性基转置矩阵就是普通的高斯消元,这时候维护线性基,每次插入一个数,更新的贡献,统计答案的时候从上往下贪心,选一个最大值,而不是回带...
Code
/************************************************************** Problem: 4184 User: BeiYu Language: C++ Result: Accepted Time:11256 ms Memory:37624 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; typedef long long LL;const int N = 5e5+50;const int M = 35; int n;map< int,int > mp;LL pow2[M],ans[N]; struct Py { LL b[M]; Py() { memset(b,0,sizeof(b)); } void insert(int x) { for(int i=M-1;~i;i--) if(x&pow2[i]) { if(!b[i]) { b[i]=x;break; } else x^=b[i]; } } LL GetAns() { LL ans=0; for(int i=M-1;~i;i--) if((ans^b[i])>ans) ans^=b[i]; return ans; }}piyan;struct SegMentTree { vector< int > d[N<<2]; #define lc (o<<1) #define rc (o<<1|1) #define mid ((l+r)>>1) void insert(int o,int l,int r,int L,int R,int x) { if(L<=l && r<=R) return void(d[o].push_back(x)); if(L<=mid) insert(lc,l,mid,L,R,x); if(R>mid) insert(rc,mid+1,r,L,R,x); } void DFS(int o,int l,int r,Py py) { for(vector< int > ::iterator i=d[o].begin();i!=d[o].end();i++) py.insert(*i); if(l==r) return void(ans[l]=py.GetAns()); DFS(lc,l,mid,py),DFS(rc,mid+1,r,py); }}seg; inline int in(int x=0,char ch=getchar(),int v=1) { while(ch>‘9‘ || ch<‘0‘) v=ch==‘-‘ ? -1 : v,ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x*v;}int main() { n=in(); for(int i=1;i<=n;i++) { int x=in(); if(x>=0) mp[x]=i; else x=-x,seg.insert(1,1,n,mp[x],i-1,x),mp.erase(x); } for(map< int,int > ::iterator i=mp.begin();i!=mp.end();i++) if((*i).second) seg.insert(1,1,n,(*i).second,n,(*i).first); pow2[0]=1;for(int i=1;i<M;i++) pow2[i]=pow2[i-1]<<1; seg.DFS(1,1,n,piyan); for(int i=1;i<=n;i++) printf("%lld\n",ans[i]); return 0;}
BZOJ 4184: shallot
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。