bzoj 4184 shallot——线段树分治+线性基

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4184

本来想了可持久化trie，不过空间是 nlogn (出一个节点的时候把 tot 复原就能做到)，时间是 nlogn 的，不太可过。

查了查发现就是线性基。因为新增一些数的话，线性基只会变大，所以可以很方便地栈序撤销。不过这样时间是不是还是 nlogn ？

现性基求最大值是看看异或上这个位上的数，答案能否变大。能的话就异或上。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#include<vector>

#define ls Ls[cr]

#define rs Rs[cr]

#define pb push_back

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

const int N=5e5+,M=N<<,K=;

int n,tot,tp[N],Ls[M],Rs[M],b[K+],bin[K+];

map<int,int> mp;

vector<int> vt[M],cg[M];

void build(int l,int r,int cr)

{

  if(l==r)return; int mid=l+r>>;

  ls=++tot; build(l,mid,ls);

  rs=++tot; build(mid+,r,rs);

}

void ins(int l,int r,int cr,int L,int R,int k)

{

  if(l>=L&&r<=R){vt[cr].pb(k);return;}

  int mid=l+r>>;

  if(L<=mid)ins(l,mid,ls,L,R,k);

  if(mid<R)ins(mid+,r,rs,L,R,k);

}

void ins(int k,int cr)

{

  for(int t=K;t>=;t--)

    {

      if(!(k&bin[t]))continue;

      if(b[t])k^=b[t];

      else{ b[t]=k; cg[cr].pb(t); return;}

    }

}

void dfs(int cr)

{

  if(!cr)return;

  int sz=vt[cr].size();

  for(int i=;i<sz;i++)

    ins(vt[cr][i],cr);

  if(!ls)

    {

      int ans=;

      for(int t=K;t>=;t--)

    if((ans^b[t])>ans)ans^=b[t];

      printf("%d\n",ans);

    }

  else dfs(ls),dfs(rs);

  sz=cg[cr].size();

  for(int i=;i<sz;i++)b[cg[cr][i]]=;

}

int main()

{

  bin[]=;for(int i=;i<=K;i++)bin[i]=bin[i-]<<;

  n=rdn();

  tot=;build(,n,);

  for(int i=,d;i<=n;i++)

    {

      d=rdn();

      if(d>) mp[d]=i,tp[i]=d;

      else ins(,n,,mp[-d],i-,-d),tp[mp[-d]]=;

    }

  for(int i=;i<=n;i++)

    if(tp[i])ins(,n,,i,n,tp[i]);

  dfs(); return ;

}