Bzoj 4184 shallot

如果隻有插入的話，直接維護線性基就好了

但是現在有了删除，我們按時間分治，将操作建立成一個線段樹。每一個數都有一個存活的區間，我們線上段樹上更新這個區間。然後dfs線段樹。線段樹上每個節點維護的是到當這個節點的線性基。然後就可以免去删除操作了

具體見代碼

#include<vector>
#include<map>
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = ;

vector<int> oper[maxn * ];

#define root 1,n
#define lson l,m
#define rson m+1,r
#define Mid int m = (l + r) >> 1
#define Now int l,int r

int ID(int l, int r) {  
    return l + r | (l != r);  
}
void insert(Now,int il,int ir,int v){
    int o = ID(l,r);
    if(il <= l && r <= ir){
        oper[o].push_back(v);
        return;
    }
    Mid;
    if(il <= m) insert(lson,il,ir,v);
    if(m+<=ir) insert(rson,il,ir,v);
}

struct Info{
    int bas[];
    void init(){
        memset(bas,,sizeof(bas));
    }
    void add(int x){
        for(int i = ;i>=;i--) {
            if((x>>i)&) {
                if(bas[i]) x^=bas[i];
                else {
                    bas[i]=x;
                    break;
                }
            }
        }
    }
    int que(){
        int ans = ;
        for(int i = ;i>=;i--) ans = max(ans,ans^bas[i]);
        return ans;
    }
    void cpy(Info & v){
        for(int i =  ; i <= ; i ++){
            bas[i] = v.bas[i];
        }
    }
}info[];
int nex[],head,tail;
void init(){
    head = ,tail = -;
    for(int i =  ; i <  ; i ++)
        nex[i] = i + ;
    nex[tail] = -;
}
int newInfo(){
    info[head].init();
    int ret = head;
    head = nex[head];
    return ret;
}
void deleteInfo(int st){
    nex[tail] = st;
    nex[st] = -;
    tail = st;
}

stack<int> S;
void dfs(Now){
    int o = ID(l,r),st = newInfo();
    info[st].cpy(info[S.top()]);
    S.push(st);
    for(vector<int>::iterator it = oper[o].begin(); it != oper[o].end();it++) 
        info[st].add(*it);
    if(l == r) printf("%d\n",info[st].que());
    else{
        Mid;
        dfs(lson),dfs(rson);
    }
    deleteInfo(st);
    S.pop();
}

map<int,int> M;

int main(){
    int n;
    scanf("%d",&n);
    int x;
    for(int i = ; i <= n ; i ++){
        scanf("%d",&x);
        if(x > ) M[x] = i;
        else{
            insert(root,M[-x],i-,-x);
            M.erase(-x);
        }
    }
    for(map<int,int>::iterator ite = M.begin();ite != M.end();ite++) 
        insert(root,ite->second,n,ite->first);
    init();
    int rot = newInfo();
    S.push(rot);
    dfs(root);
    return ;
}