「BZOJ4184」shallot - 线段树分治 + 线性基

简要题意

对一个可重集 A 进行下列操作:

  1. 插入一个数
  2. 删除一个数
  3. 询问 A 的子集的最大异或和

操作数为 5\times 10^5

黑暗爆炸oj link: #4184. shallot

#4184. shallot

Description

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

每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗,并且

让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。

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

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

Input

第一行一个正整数n表示总时间;第二行n个整数a1,a2...an,若ai大于0代表给了小葱一颗数字为ai的小葱苗,否则代表从小葱手中拿走一颗数字为-ai的小葱苗。

Output

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

Sample Input

1
2
6
1 2 3 4 -2 -3

Sample Output

1
2
3
4
5
6
1
3
3
7
7
5

Hint

N<=500000,Ai<=2^31-1

Source

题解

显然是线性基题目,但是由于删除操作的存在并不好处理线性基,直接暴力是不行的

有插入,删除操作而且并不是强制在线,于是考虑离线做法

使用 std::set 维护当前点的插入时间 p ,在删除时间 q 的时候相当于对 [p,q) 进行区间插入一个元素,从而把插入删除变为了区间加入。然后直接进行线段树即可

代码十分好写

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#define ul unsigned long long

const int N = 500000 + 100;
const int logN = 32;

struct lb {
int siz;
ul base[logN + 2];

void insert (ul x) {
down (i, logN, 0)
if ((x >> i) & 1){
if (base[i]) x ^= base[i];
else {
base[i] = x;
break;
}
}

}

ul query (ul x) {
down (i, logN, 0) {
x = std::max(x, x ^ base[i]);
}
return x;
}
void clear() { mem(base); siz = 0; }
};

struct Seg {
std::vector <ul> seg[N * 3];
void modify (int o, int l, int r, ul x, int ql, int qr) {
if (ql <= l && r <= qr) {
seg[o].pb(x);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) modify (o << 1, l, mid, x, ql, qr);
if (mid < qr) modify (o << 1 | 1, mid + 1, r, x, ql, qr);
}

void query (int o, int l, int r, lb ret) {
for (auto i : seg[o]) ret.insert(i);
if (l == r) {
print(ret.query(0)), putchar('\n');
return;
}
int mid = (l + r) >> 1;
query (o << 1, l, mid, ret);
query (o << 1 | 1, mid + 1, r, ret);
}
} tr;

std::set <std::pair <ul, int> > s;
int main () {
int n = read(), x;
up (i, 1, n) {
x = read();
if (x > 0) s.insert(mp(x, i));
else {
auto it = s.lower_bound(mp(-x, 0));
tr.modify(1, 1, n, -x, it->second, i - 1);
s.erase(it);
}
}
for (auto i : s) tr.modify(1, 1, n, i.first, i.second, n);
lb t; t.clear();
tr.query (1, 1, n, t);
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!