A simple Blog for wyx I've been down the bottle hoping.
4184: shallot 线段树 线性基
发表于: | 分类: Oi | 评论:0 | 阅读:47

首先你需要明白一个事情就是线性基这个东西可以随便插入但是并不支持删除

然后你就需要设计一个结构只有插入

利用时间线段树即可,用线段树维护时间顺序,然后每个节点的东西是在这段时间内进行的插入的元素

每个叶子节点对应了一个答案,所以到叶子节点输出就行了

一个细节是一个物品没有出现当且仅当他彻底被删除,也就是说如果一个东西出现了多次的话只有都删除的时候才能彻底算作截止

然后就是码码码了


#include <set>
#include <map>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define pb push_back
const int N = 5e5+5;
const int M = N << 2;
 
inline 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<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}
 
struct data {
    int val[33];
    data () {
        memset(val, 0, sizeof val);
    }
    void operator += (int x) {
        for(int i=30;~i;--i) {
            if((1<<i)&x) {
                if((1<<i)&val[i]) x ^= val[i];
                else {
                    val[i] = x;
                    break;
                } 
            }
        }
    }
 
    inline int get_max() {
        int now = 0;
        for(int i=30;~i;--i) {
            if((1<<i)&val[i] && !((1<<i)&now)) now ^= val[i]; 
        }
        return now;
    }
}Ans;
 
vector <int> tr[M];
 
inline void change(int k,int l,int r,int x,int y,int val) {
    if(l==x && r==y) {
        tr[k].pb(val);
        return;
    }
    int mid = (l+r) >> 1;
    if(y <= mid) change(k<<1,l,mid,x,y,val);
    else if(x > mid) change(k<<1|1,mid+1,r,x,y,val);
    else change(k<<1,l,mid,x,mid,val), change(k<<1|1,mid+1,r,mid+1,y,val);
}
 
inline void solve(int k,int l,int r,data C) {
    vector <int> :: iterator it;
    for(int i=0;i<tr[k].size();++i) C += tr[k][i];
    if(l==r) {
        printf("%d\n", C.get_max());
        return ;
    }
    int mid = (l+r) >> 1;
    solve(k<<1,l,mid,C);
    solve(k<<1|1,mid+1,r,C);
}
 
set <int> s;
map <int,int> cnt, last;
 
int main() {
//  freopen("tt.in","r",stdin);
    int n = read();
    for(int i=1;i<=n;++i) {
        int x = read();
        if(x > 0) {
            cnt[x] ++;
            if(cnt[x] == 1) last[x] = i;
            s.insert(x);
        }
        else {
            cnt[-x] --;
            if(cnt[-x] == 0) change(1,1,n,last[-x],i-1,-x); 
//          cout << last[-x] << " " << i-1 << " " << -x << endl;
            s.erase(s.find(-x));
        }
    }
    set <int> :: iterator it;
    for(it = s.begin(); it != s.end(); ++it) {
        int tmp = (*it);
        change(1,1,n,last[tmp],n,tmp);
//      cout << last[tmp] << " " << n << " " << tmp << endl;
    }
    solve(1,1,n,Ans);
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP