[BZOJ4184] shallot (线段树分治+线性基)

[BZOJ4184] shallot (线段树分治+线性基)

题目

小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。

每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。

这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为Oi选手的你，你能帮帮他吗？

你只需要输出最大的异或和即可，若小葱手中没有小葱苗则输出0。

Input
第一行一个正整数 n n n表示总时间；第二行 n n n个整数 a 1 , a n an an，若 a i ai ai大于 0 0 0代表给了小葱一颗数字为 a i ai ai的小葱苗，否则代表从小葱手中拿走一颗数字为 − a i -ai −ai的小葱苗。

Output
输出共 n n n行，每行一个整数代表第i个时刻的最大异或和。

思路

首先，得到这个异或最大值，我们会想到使用线性基。对于线性基中的插入，我们可以处理，但是删除的话，我们就没有办法处理。若是重建会T，我们就需要使用线段树分治。

Code：

#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 500005
#define LL long long
#define Int register int
using namespace std;
inline void read(LL &x)
{x = 0;LL f = 1;char s = getchar();while (s < '0' || s > '9'){if (s == '-')f = -1;s = getchar();}while (s >= '0' && s <= '9'){x = (x << 3) + (x << 1) + (s ^ 48);s = getchar();}x *= f;
}
LL a[MAXN];
struct XXJ
{LL F[32];inline void Insert(LL x){for (Int i = 31; i >= 0; -- i){if ((x >> i) & 1){if (! F[i]){F[i] = x;break;}x ^= F[i];}}}inline LL Max_Xor(){LL Ans = 0;for (Int i = 31; i >= 0; -- i)if ((Ans ^ F[i]) > Ans)Ans ^= F[i];return Ans;}
}Get;
map<LL, LL> Map;
map<LL, LL> Mapl;
struct node
{LL l, r, Val;node(){}node(LL L,LL R,LL VAL){l = L;r = R;Val = VAL;}
};
vector<node> G;
void Divide_Tree(LL l,LL r,vector<node> Hav,XXJ Ans)
{int Len = Hav.size();for (Int i = 0; i < Len; ++ i)if (Hav[i].l == l && Hav[i].r == r)Ans.Insert( Hav[i].Val );if (l == r){printf("%lldn", Ans.Max_Xor());return ;}LL Mid = (l + r) / 2;vector<node> Tl, Tr;for (Int i = 0; i < Len; ++ i)if (Hav[i].l != l || Hav[i].r != r){if (Hav[i].r <= Mid)Tl.push_back( Hav[i] );else if (Hav[i].l > Mid)Tr.push_back( Hav[i] );else{Tl.push_back(node(Hav[i].l, Mid, Hav[i].Val));Tr.push_back(node(Mid + 1, Hav[i].r, Hav[i].Val));}}Divide_Tree(l, Mid, Tl, Ans);Divide_Tree(Mid + 1, r, Tr, Ans);
}
int main()
{LL n;read( n );for (Int i = 1; i <= n; ++ i){LL x;read( x );if (x > 0){if (++ Map[x] == 1)Mapl[x] = i;}else{if (-- Map[- x] == 0)G.push_back(node(Mapl[- x], i - 1, - x)); }}map<LL, LL>::iterator item;for (item = Map.begin(); item != d(); item ++)if (item -> second > 0)G.push_back(node(Mapl[item -> first], n, item -> first));Divide_Tree(1, n, G, Get);return 0; 
}