【bzoj4184】shallot（线段树+线性基）

【bzoj4184】shallot（线段树+线性基）

Description

小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。

每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且

让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。

这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为Oi选手的你，你能帮帮他吗？

你只需要输出最大的异或和即可，若小葱手中没有小葱苗则输出0。

Input

第一行一个正整数n表示总时间；第二行n个整数an，若ai大于0代表给了小葱一颗数字为ai的小葱苗，否则代表从小葱手中拿走一颗数字为-ai的小葱苗。

Output

输出共n行，每行一个整数代表第i个时刻的最大异或和。

Sample Input

6
1 2 3 4 -2 -3

Sample Output

1
3
3
7
7
5

HINT

 N<=500000,Ai<=2^31-1

题解：

最大异或和第一个想到的就是线性基。

由于线性基无法进行删除操作，所以我们考虑离线。

我们可以以时间来建一棵线段树，给每个线段树的节点开一个vector，存储这个节点所包含有哪些数。将每一次插入和删除同一个数看做一个个的区间进行修改。注意要用到标记永久化。最后遍历整棵线段树，用线性基求出每一个时间的答案。具体请看代码。

如果有误在评论区吼一声哦！

#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,tot,a[500010],lsh[500010],head[500010],nxt[500010],last[500010];
vector<int>Seg[2000010];
struct xxj{int a[35];xxj(){memset(a,0,sizeof(a));}void insert(int x){for(int i=30;i>=0;i--){if(x&(1<<i)){if(a[i]){x^=a[i];if(!x)return;}else{a[i]=x;return;}}}return;}int getmax(){int ans=0;for(int i=30;i>=0;i--)if((ans^a[i])>ans)ans^=a[i];return ans;}
};
int rd(){int x=0,y=1;char c;do{c=getchar();if(c=='-')y=-y;}while(!isdigit(c));do{x=(x<<1)+(x<<3)+(c^48);c=getchar();}while(isdigit(c));return x*y;
}
void update(int o,int l,int r,int L,int R,int v){if(L<=l&&r<=R){Seg[o].push_back(v);return;}int mid=(l+r)>>1;if(L<=mid)update(o<<1,l,mid,L,R,v);if(R>mid)update(o<<1|1,mid+1,r,L,R,v);return;
}
void Query(int o,int l,int r,xxj a){for(int i=0;i<Seg[o].size();i++)a.insert(Seg[o][i]);if(l==r){printf("%dn",a.getmax());return;}int mid=(l+r)>>1;Query(o<<1,l,mid,a);Query(o<<1|1,mid+1,r,a);return;
}
int main(){memset(Seg,NULL,sizeof(Seg));n=rd();for(int i=1;i<=n;i++)lsh[i]=labs(a[i]=rd());sort(lsh+1,lsh+n+1);m=unique(lsh+1,lsh+n+1)-(lsh+1);for(int i=1;i<=n;i++){int d=lower_bound(lsh+1,lsh+m+1,labs(a[i]))-lsh;if(a[i]>0){if(!head[d])head[d]=last[d]=i;else{nxt[last[d]]=i;last[d]=i;}}else{update(1,1,n,head[d],i-1,-a[i]);head[d]=nxt[head[d]];}}for(int i=1;i<=m;i++){if(lsh[i]==lsh[i-1]||!head[i])continue;update(1,1,n,head[i],n,lsh[i]);}xxj o;Query(1,1,n,o);return 0;
}