BZOJ 4184 shallot

发布于 2017-08-14  155 次阅读


题面:http://www.lydsy.com/JudgeOnline/problem.php?id=4184

题意:带插入删除动态维护异或最大值。


如果仅有插入操作,线性基就可以完美解决,但是有了删除操作,怎么办呢?

利用线段树对时间分治,处理出每个数存在的区间,在线段树上对应点存到 vector 里,这样我们可以去 dfs 线段树,在从根走到叶子的过程就都是插入操作了。

走到一个叶子之后呢?我们可以直接继承父亲节点的线性基,就相当于执行了删除操作。

貌似数据并不存在有多个相同的数删除了一个的情况,好方便啊。T.T

这题突然在晚上睡觉的时候想明白了... 结果早上写一发,最开始考虑的对于线段树上的每一个节点都存一个线性基,然而内存无法接受。

实际上只需要动态下传一个线性基即可。

 


一个非常弱的准退役OIER