BZOJ4184 Shallot <线段树分治+凸包>

Problem

Shallot

$\mathrm{Time\;Limit:\;30\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。
每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。
这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为$\mathrm{OI}$选手的你，你能帮帮他吗？
你只需要输出最大的异或和即可，若小葱手中没有小葱苗则输出0。

Input

第一行一个正整数$n$表示总时间。
第二行$n$个整数$a_1,a_2,\cdots,a_n$，若$a_i$大于$0$代表给了小葱一颗数字为$a_i$的小葱苗，否则代表从小葱手中拿走一颗数字为$-a_i$的小葱苗。

Output

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

Sample Input

6
1 2 3 4 -2 -3

Sample Output

1
3
3
7
7
5

HINT

$n\le 5\times10^5$，$a_i\le2^{31}-1$。

标签：线段树分治 线性基

Solution

线性基只支持插入，不支持删除，而每个数的存在时间为一个区间，于是需要用线段树分治。
将每个数存在的时间区间预处理出来，分为$\log{n}$个插入线段树的$\log{n}$个结点中。然后遍历一遍线段树，处理出每个点到根的路径上所有数组成的线性基（即其父亲的线性基插入在这个点上的所有数）。当访问到长度为$1$的区间时，即可回答当前时间点的询问。总时间复杂度$O(32\times n\log{n})$。

Code

#include <bits/stdc++.h>
#define fir first
#define sec second
#define MAX_N 500000
#define mid ((s+t)>>1)
using namespace std;
typedef map<int,int>::iterator IT;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n;
map <int, int> mrk, lst;
vector <int> tr[MAX_N<<2];
struct Basis {int b[31];} init;
void insert(Basis &B, int x) {
    for (int i = 30; ~i; i--) if (x>>i&1) {
        if (B.b[i]) x ^= B.b[i];
        else {B.b[i] = x; break;}
    }
}
int query(Basis B) {
    int ret = 0;
    for (int i = 30; ~i; i--)
        ret = max(ret, ret^B.b[i]);
    return ret;
}
void insert(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {tr[v].push_back(x); return;}
    if (l <= mid) insert(v<<1, s, mid, l, r, x);
    if (r >= mid+1) insert(v<<1|1, mid+1, t, l, r, x);
}
void bi_solve(int v, int s, int t, Basis B) {
    for (int i = 0; i < (int)tr[v].size(); i++) insert(B, tr[v][i]);
    if (s == t) {printf("%d\n", query(B)); return;}
    bi_solve(v<<1, s, mid, B), bi_solve(v<<1|1, mid+1, t, B);
}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) {
        int x; read(x);
        if (x > 0) {if (!mrk[x]++) lst[x] = i;}
        else {if (!--mrk[-x]) insert(1, 1, n, lst[-x], i-1, -x);}
    }
    for (IT it = mrk.begin(); it != mrk.end(); it++)
        if (it->sec) insert(1, 1, n, lst[it->fir], n, it->fir);
    return bi_solve(1, 1, n, init), 0;
}