BZOJ 4184 shallot
假的题面
可用的题面
离线BZOJ好啊
- 解题思路
- 裸的想法
- 优化一下线性基的储存
- 另外两种优化思路
- 源代码
解题思路
根据标签可知,这题要用线段树维护。
裸的想法
线段树上每个点都是一个线性基,这个线段树就维护时间轴。对于时间轴上的某一点,线段树维护的是这个点时可用的数字构成的线性基。我们可以在取出某个数字的时候,将它加到线段树上对应的时间段。但是会发现pushdown和pushup极慢,而且很不方便,于是标记永久化(我再才第一次使用标记永久化这个科技),在查询的时候统计标记。实测下来,20个点里有一半的数据量达到最大值。这个思路在大些的这一半测试点上,占用内存约148MB,耗时2s左右,20个点全部跑下来需要20s,于是显然MLE了,要不是BZOJ只看总时间,那还TLE了。下面这个是使用传统的线性基的MLE代码——
#include
优化一下线性基的储存
()实测那个博主的代码跑大的测试点时内存约72MB,时间都在2.3s左右。内存少了一半。
可以想象,由于标记永久化和区间长度不大,线段树上那些线性基,会有很多空行,有些线性基甚至是全空的,于是弃用固定长度为33的int
数组表示每一个线性基,换用变长数组vector。这样的线性基,数组下标为\(i\)的那一个向量,最高位的1就不一定在从右向左第\(i\)位上了。换句话说,这种新的线性基,可以看成把原来那种线性基里的0向量全部去掉,剩下的全是非0向量。
从那个链接里学到了新的线性基插入方法,可以在这种变长数组的情况下插入元素——依然从高到低(从大到小)扫描线性基中已有的向量\(p[i]\),和想要插入的元素\(x\)对比,如果\((x \text^ p[i])
结合代码看一下这个过程——
std::vector p;
void insert(int x)
{
for(int i=p.size()-1;~i;i--)
if((p[i]^x)
我来尝试说明一下,两种处理\(x\)的方法是等效的。
回忆一下传统的线性基里,向量\(p[i]\)如果是非零向量,那么其二进制第\(i\)位(同时也是其最高位)一定是1,换句话说,线性基里的所有行向量的最高位1一定排在线性基组成的01矩阵的主对角线上。
我们在传统线性基中插入数字\(x\)时,如果\(x\)第\(i\)位是1,那么就让\(x\)异或上\(p[i]\),使\(x\)在这一位的1被去掉。由于从高到低处理,所以\(x\)在这个过程被处理的总是最高位,最高位总是不断向后退,\(x\)总是变小。这个过程持续到\(x\)变为0,或者发现线性基里没有这一位为1的向量,无法把\(x\)最高位清零,于是就把\(x\)塞到这个位置,\(x\)的最高位1现在依然在主对角线上。
在压缩过的线性基里插入数字\(x\),依然从高到低扫。如果向量\(p[i]\)能够减小\(x\),那就两种情况——
-
p[i]的最高位和x的最高位位置一致
- 这种大概就是传统线性基里的操作了吧,将x的当前最高位清零,x肯定变小了。
-
p[i]的最高位低于x的最高位
-
出现这种情况,说明比p[i]大的那些向量都没能把x的当前最高位清零,那么p[i]和比p[i]小的向量更不可能清零x的当前最高位了,x能加入线性基是石锤了。这时候x=p[i],让x变成了xp[i],仅只是通过清零了x的一部分低位,让x减小,对x的最高位没有影响。这时直接将\(x\)push_back进去得到的新线性基,和将\(x\)处理到最后一个向量p[i]再push_back得到的线性基是等价的。所以可以及时break出来,剩下那些更小的向量都不用看了。 没有及时break,所以这里还可以继续优化一下——
std::vector
p; void insert(int x) { for(int i=p.size()-1;~i;i--) { if((p[i]^x) 最慢的点2.25s,其他大的测试点基本2.13s,差不多优化了0.2s,感觉效果还是挺好的。
-
-
p[i]的最高位不可能高于x的最高位,那样不能减小x。
另外两种优化思路
-
大的测试点69MB、1.7s
首先是使用了快读。
在处理输入数据时使用sort、unique、lower_bound这套进行离散化,而不用速度慢的map。
把线段树上的节点从线性基换成vector,更新区间时直接将数字push_back进对应线段树节点的vector里,而不是把数字塞进几个线性基。
查询时收集标记是这么做的:把当前节点vector里的数字全部取出来塞到用于统计永久化标记的线性基里。
线性基多存一个变量,统计线性基内非零向量的数量,如果当前线性基向量数量已经达到32,就及时return。乍一看这个优化是最关键的,能十分有效地避免前面几个优化的缺点,但实测去掉这个优化还是1.7s…………
-
emmm……还没看懂,内存45MB左右,大的测试点耗时1.3s。。。orz…
现在这个todolist又多了一个√
- [x] CodeForces 1100F 单纯询问区间异或最大值
- [x] HDU 6579 多了个末尾插入数据的操作,还有强制在线
- [x] BZOJ 4184 这题要支持插入和删除的操作,询问是整个序列。居然是权限题……本地测一下算了。
- [ ] UVALive 8514 2017ICPC西安的一道题,询问区间异或值或上k的最大值
源代码
#include