BZOJ 4942 [Noi2017] 整数

发布于 2017-11-30  625 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4942

题意:维护一个 n 位二进制数... 支持加一个 \(a \times 2^k\) 和查询单位是 0 还是 1。


这尼玛什么狗题啊... 考场上写了个\(n^2\),同时写了个其实不太对的离线,好不容易骗了 40 分....

今天重写一发,发现已经不记得了,YY 了几十秒会了一个三个 log 的鬼做法,然后由于其中一个 log 是树状数组所以期望运行速度和两个 log 的线段树差不多。自信码一下先,没准能过 BZ 总实现,结果交一发 loj 有 72pts... 交 BZ 就 T 死了。

啊,总比考试上的得分好看了一点... 然后其实只要压位就可以优化下去一个 log 然后 A 掉了,大概,写了一会非常烦躁,于是 ORZ 了比较好写的做法...

 

首先显然只有加法的话暴力进位的复杂度就是对的,均摊单次\(O(1)\),但是有减法就很烦躁,于是考虑维护两个 n 位二进制数,一个存加的,一个存减的,查询的时候两个二进制数做差就行了。

当然不用真正做差,分类讨论一下可以发现只要知道每一位是什么和两个数前这些位的大小关系即可。

维护大小关系可以上线段树,就超级好写啦... 我维护了最大一位的不同的下标是什么。

 


一个非常弱的准退役OIER