被各种题薄纱的一天。
看了题解才发现机场修建有一车复杂度优秀而且好写常数小的做法。
这么看把这个题放上去还是非常有意义的。
至少能让我想起来分块是可以用来代替树状数组的。
以及属实降智了。
菜死了怎么办菜死了怎么办菜死了怎么办菜死了怎么办菜死了怎么办菜死了怎么办菜死了怎么办菜死了怎么办菜死了怎么办菜死了怎么办菜死了怎么办菜死了怎么办。
下次有题还是要放出去的。
静等巨佬爆标。
所以这期的学术闲话。。。
是真正的学术闲话！
可能不同于之前某些中间插播了一点点学术的纯闲话。
放点有意思的东西。
首先回收一下之前某次闲话里面写的东西。
文艺平衡树那个题，用强制在线 CDQ 是可以做到 \(O(n \log n)\) 的。
具体做法参考 EI 的某训队论文。
其实就是给这 \(\log n\) 个块倒着加了个分散层叠，然后分析一波复杂度。
只能说还是见的东西太少了。
大简单题
注：数据范围和时空限制没有参考价值。读个题面就好了。
首先考虑这东西强制在线之后有什么经典做法。
首先是主席树/划分树，时空 \(O(n \log n)\)。
然后是分块，时间 \(O(n \sqrt {n \log n})\)，空间 \(O(n)\)。
然后可以用 kdt / 分散层叠优化分块，时间 \(O(n \sqrt n)\)，空间 \(O(n)\)。
然而我们知道，如果可以离线的话，是存在时间 \(O(n \log n)\) 空间 \(O(n)\) 的做法的。
这么看在线算法就太差了。
而这道题卡了空间，所以貌似只能分块。
这合理吗？
无论怎样，还是要追求一下 polylog 算法的吧。
都强制在线了，还分治个球球。
先把分治放一放，考虑平衡复杂度。
你已经是一个成熟的渐进复杂度了，该学会自己和自己平衡了。
首先考虑，我们有个东西叫分散层叠优化分块。
也就是分块，块内排序，扫每个块二分。
分散层叠是用来加速多个块二分的。
这东西的查询复杂度是 \(O(\sqrt n + \log n)\)。
这主要是因为块数是 \(O(\sqrt n)\) 的。
于是就很容易想到，我们可以调大块长。
直接把块长调到 \(O(\frac{n}{\log n})\)，这样整块查询的复杂度就变成了 \(O(\log n)\) 了。
但是散块就显得有点太大了。
没关系，遇到问题直接递归处理。
等长度小于 \(O(\log n)\) 之后直接爆扫。
好了算法流程完成了。
分析一下复杂度。
首先是查询，\(T(n) = T(\frac{n}{\log n}) + O(\log n)\)。
查询巨佬得到 \(T(n) = O(\log n)\)。
单次查询一个 \(\log\)，基本上已经是下界了。
考虑空间复杂度。
显然是 \(n\) 乘上层数。
这个层数还挺难算的。
但是我们发现这个结构等同于多叉分治 NTT。
直接套用结论，可以得到空间复杂度为 \(O(\frac{n \log n}{\log \log n})\)。
直接取 \(n = 10^6\)，发现层数不超过 5，可以认为 \(O(\frac{\log n}{\log \log n})\) 只是一个大常数。
可以说复杂度碾压主席树。
（虽然代码量也碾压主席树）
不要急，学术部分没完呢。
搞出来上述算法其实是为了另一个 简单题。
这个题同样卡了空间，结果只剩下一堆不优雅的根号算法。
但是借助 \(\log\) 分块和强制在线 CDQ，有可能可以让 polylog 算法卡过去。
做法的话其实同文艺平衡树那里。
考虑动态维护递归树，然后启发式合并。
这部分不用管复杂度自然对。
然后考虑我们现在有 \(\log n\) 个块。
每个块都可以认为是静态的二维平面。
然后使用上面那个题的做法进行预处理即可。
时间复杂度 \(O(n \log^2 n)\)，空间复杂度 \(O(\frac{n \log n}{\log \log n})\)。
没有打。希望空间可以卡过去吧。
依赖这种妙妙东西，其实树套树一类的完全被碾压了。
虽然从代码量上看这种分块很不实用的样子。
和简单题这个题已经打了很久了。
一直在想能不能做 polylog，但是之前没成功过。
强制在线 CDQ 就是这么出来的。
本来是西安的前一天晚上想起来的这个东西。
刚想出来的时候感觉好妙。
然而，过了这么几天吧。。。。
逐渐意识到无非就是多叉线段树，拿分散层叠优化了一下而已。貌似是个平凡东西。
而且空间复杂度，只能说很不错了，但是感觉仍然不是很满意。
毕竟没有做到线性。
渐渐感觉这东西比较水了。
jjdw 是不是给我推过成神之日来着。
（准备引用一句话。）
（但是如果看过的话似乎也知道我想说什么了，没看过那不知道就不知道吧。）
（所以不写在这里了。）
感觉学 OI 过程中很多东西都是这样子的吧。
比如这东西。本来看名字和颜色以为是什么神仙科技来着。
然而 APJ 给我两分钟讲完了。
只能说原理简单实现容易。
我学 OI 主要靠的是兴趣来着。
而很大的组成元素就是 OI 中各种神仙东西。
然而事实证明这东西并不足够持久。
按逻辑往下，下文会是什么？
通过一堆推导得到另一个支柱？
然而并不是。
还有一些其他的问题需要解决。
因为还没想明白，所以后面不写了。
已经忘掉了学 OI 是什么样子的了。
好像最近一直都在专心研究某一个小部分。
其他部分完全没咋碰。例如这两天的 DP （尤其是数位DP）一点不会。
感觉更像学术而不是竞赛。
就像之前的 joke 和现在的 gtm 一样。
但是也许并不重要吧。
看到了更多更本质的东西。也算没有白浪费时间了。
之后？
你觉得我会去安心补计数吗。
说不好，看心情。
来这里之后脑子要停了。。。。
感觉一个主要原因是困。
或许是生活条件变好了，不再考虑以后了？
不好评价。
但是我的意见是确实可以先停一停。
毕竟回去之后的时间还有一年，这边的时间却只有半个月。
多见点新东西总是比自己乱想要好的吧。