bzoj 4184: shallot 分治+线性基

bzoj 4184: shallot 分治+线性基

题意

小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。
每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。
这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为Oi选手的你，你能帮帮他吗？
你只需要输出最大的异或和即可，若小葱手中没有小葱苗则输出0。
N<=500000,Ai<=2^31-1

分析

其实就是要资瓷加入一个数或删除一个数，每次操作后询问最大异或值。
显然每一个数可以影响的时间实际上是一个区间，我们先离线把所有区间都找出来。
找最大异或值的经典做法是维护线性基，但线性基不资瓷删除操作。
一开始我想的是用线段树来维护，树上的每一个节点维护一个线性基。对于每一个区间，将其在线段树上的对应节点上的线性基加入这个数，然后对于一个位置的线性基，就是把根节点到其对应叶节点路径上所有线性基合并起来。那么就可以做到nlog^2了。
后来一想发现其实不用写线段树，只要用分治来实现就好了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;const int N=500005;int n,a[N],w[N],ans[N],bin[35],cnt;
struct data{int a[35];}bas;
struct edge{int l,r,w;}e[N];
vector<int> vec[N];int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}void ins(data &bas,int x)
{for (int i=30;i>=0;i--)if (x&bin[i]){if (!bas.a[i]){bas.a[i]=x;break;}x^=bas.a[i];}
}void solve(int l,int r,int L,int R,data bas)
{if (l==r){for (int i=L;i<=R;i++) ins(bas,e[i].w);for (int i=30;i>=0;i--) ans[l]=max(ans[l],ans[l]^bas.a[i]);return;}for (int i=L;i<=R;i++) if (e[i].l<=l&&e[i].r>=r) ins(bas,e[i].w);int now=L-1,mid=(l+r)/2;for (int i=L;i<=R;i++)if ((e[i].l>l||e[i].r<r)&&max(e[i].l,l)<=min(e[i].r,mid)) now++,swap(e[now],e[i]);solve(l,mid,L,now,bas);now=L-1;for (int i=L;i<=R;i++)if ((e[i].l>l||e[i].r<r)&&max(e[i].l,mid+1)<=min(e[i].r,r)) now++,swap(e[now],e[i]);solve(mid+1,r,L,now,bas);
}int main()
{bin[0]=1;for (int i=1;i<=30;i++) bin[i]=bin[i-1]*2;n=read();for (int i=1;i<=n;i++) a[i]=read(),w[i]=abs(a[i]);sort(w+1,w+n+1);int w1=unique(w+1,w+n+1)-w-1;for (int i=1;i<=n;i++){int pos=lower_bound(w+1,w+w1+1,abs(a[i]))-w;if (a[i]>=0) vec[pos].push_back(i);else e[++cnt].l=vec[pos][vec[pos].size()-1],e[cnt].r=i-1,e[cnt].w=-a[i],vec[pos].pop_back();}for (int i=1;i<=w1;i++)for (int j=0;j<vec[i].size();j++)e[++cnt].l=vec[i][j],e[cnt].r=n,e[cnt].w=a[e[cnt].l];solve(1,n,1,cnt,bas);for (int i=1;i<=n;i++) printf("%dn",ans[i]);return 0;
}