【BZOJ4184】shallot

2016.03.19 15:30 Sat | 43次阅读 | 旧日oi | 固定链接 | 源码

题解

分治(线段树)+线性基

对于这种动态图,动态数列的问题,一个大杀器就是把每个点存在的时间找出来,然后扔到线段树里或者离线维护,以一个log的代价去掉删除操作
在这道题里我们可以发现,对于一段区间,我们要求出它的线性基。但是用线段树存的话虽然好想,但是容易MLE,所以我们动态的来稿,这样空间复杂度有保障。
先处理出每个数出现的区间,然后进入分治过程(l,r,v,a),v是此时的线性基数组,a是存在于这个[l,r]之间的数的集合。
我们把a中存在的区间恰好是[l,r]的数加到线性基里,其它的数按照mid分别加到左边区间,右边区间或者都加,然后分治两边就可以了。
本质上和线段树是相同的。

my code

#include <bits/stdc++.h>
using namespace std;
#define N 500005
int n;
map<int,int> pos,now;
struct node
{
    int a[31];
    void insert(int x)
    {
        for(int i=30;i>=0;i--)
        if(x>>i&1)
        {
            if(a[i]) x^=a[i];
            else {a[i]=x;break;}
        }
    }
    int query()
    {
        int re=0;
        for(int i=30;i>=0;i--) re=max(re,re^a[i]);
        return re;
    }
    node(){}
}st;
vector< pair<pair<int,int>,int> > a;
void work(int l,int r,node v,vector< pair<pair<int,int>,int> > a)
{
    int mid=l+r>>1;
    vector< pair<pair<int,int>,int> > tl,tr;tl.clear();tr.clear();
    for(int i=0;i<a.size();i++)
    {
        if(a[i].first.first==l&&a[i].first.second==r) v.insert(a[i].second);
        else if(a[i].first.second<=mid) tl.push_back(a[i]);
        else if(a[i].first.first>mid) tr.push_back(a[i]);
        else 
        {
            tl.push_back(make_pair(make_pair(a[i].first.first,mid),a[i].second));
            tr.push_back(make_pair(make_pair(mid+1,a[i].first.second),a[i].second));
        }
    }
    if(l==r){printf("%d\n",v.query());return;}
    work(l,mid,v,tl);work(mid+1,r,v,tr);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n;
    for(int x,i=1;i<=n;i++) 
    {
        scanf("%d",&x);
        if(x>0)
        {
            if(now[x]==0) pos[x]=i;
            now[x]++;
        }
        else if(x<0)
        {
            if(now[-x]==1) a.push_back(make_pair(make_pair(pos[-x],i-1),-x)),pos[-x]=0; 
            now[-x]--;
        }
    }
    for(map<int,int>::iterator it=pos.begin();it!=pos.end();it++)
    if(it->second) a.push_back(make_pair(make_pair(it->second,n),it->first));
    work(1,n,st,a);
}