【BZOJ4184】Shallot 题解
BZOJ权限题，给一下题面：
Description
小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。
每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。
这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为Oi选手的你，你能帮帮他吗？
你只需要输出最大的异或和即可，若小葱手中没有小葱苗则输出0。
Input
第一行一个正整数n表示总时间；第二行n个整数a1,a2…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
题解
线性基并不支持删除操作，这就使得本题非常糟糕
考虑到每个数字有一定的存在时间，换句话说，它只对时间在[l,r]区间有影响，于是可以用线段树对时间进行维护。每个结点开一个vector来存储对这段时间有影响的数字，询问时下传vector
具体地说，每碰到一个插入操作，我们存下它的值与时间；碰到一个删除操作，找到之前这个值出现的时间，然后将这个数字插入对应时间段的vector里面。为了寻找某个值出现的时间，需要用一个set来维护一下
询问就是先序遍历整颗树，每到一个结点就进行vector下传操作。但是这样并不是很优秀，空间复杂度可能承受不住。如果动态释放内存，则时间复杂度可能承受不住。
我们可以遍历时传递一个参量，表示从根到当前点所经过的所有vector里面的所有数的线性基，显然这个参量的空间复杂度是log级别的。每到一个结点，就把这个结点的vector里面的所有数往线性基里面插，然后再往下搜的时候就传入插完后的线性基
遍历到叶子结点，对这个线性基做一次Max询问就是对应的答案了。似乎这个答案并不需要存，可以直接输出？好像遍历到叶子结点的顺序就是时间顺序？然而我傻逼了，开了个数组来存……
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=500010;
vector<int> num[N<<2];
struct base
{
int a[35];
base(){memset(a,0,sizeof(a));}
int& operator [] (const int &x){return a[x];}
} c;
set<pii> S;
set<pii>::iterator it;
int ans[N];
void insert(base &a,int x)
{
for(int i=30;i>=0;i--)
if(x&(1<<i))
{
if(a[i]) x^=a[i];
else{a[i]=x;break;}
}
}
int query(base &a)
{
int ans=0;
for(int i=30;i>=0;i--)
if((ans^a[i])>ans) ans^=a[i];
return ans;
}
void insert(int o,int l,int r,int nl,int nr,int x)
{
if(l>=nl&&r<=nr){num[o].push_back(x);return;}
int mid=(l+r)/2;
if(nl<=mid) insert(o*2,l,mid,nl,nr,x);
if(nr>mid) insert(o*2+1,mid+1,r,nl,nr,x);
}
void dfs(int o,int l,int r,base bs)
{
for(int i=0;i<num[o].size();i++)
insert(bs,num[o][i]);
if(l==r){ans[l]=query(bs);return;}
int mid=(l+r)/2;
dfs(o*2,l,mid,bs);
dfs(o*2+1,mid+1,r,bs);
}
int main()
{
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
if(x>0) S.insert(pii(x,i));
else
{
it=S.lower_bound(pii(-x,0));
insert(1,1,n,it->second,i-1,it->first);
S.erase(it);
}
}
for(it=S.begin();it!=S.end();it++)
insert(1,1,n,it->second,n,it->first);
dfs(1,1,n,c);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}