数据结构只因屑化-526互联

好像一直在做这个。
然而。。。。

越来越感觉这个东西不适合用来打 OI 了。
虽然还没有整出来。
只是用来确保复杂度还差不多。
也就是学术用途吧（?）

大致的思想朴素而不完备。
主要适用于偏序类的东西，或者区间第 k 大之类的伪不可合并信息。

枚举每一维，整一个高维树套树。
对于单增/不带修的维，放至最外层。
对于这种情况可以考虑使用可持久化进行优化。
对于修改/查询不常规的，尽可能放至外层。

同时，为了确保空间复杂度，还需要结合连续段/虚树之类的技巧。
如果需要二分但是可供使用的复杂度不足一个 \(\log n\)，那就考虑分散层叠优化。
这东西序列上能跑，树上也能跑。
或者是调换到外维。这个做法的题也遇到过。

另外，可以把这个过程转成分治实现。空间复杂度消掉好多。

然而，实际上仍然需要自行考虑很多问题。
上述框架只是废话。

整点题。看一看这东西是怎么随手整出来 500+ 的代码量的。

好好好，树链问题。
待修区间第 K 大。由于可合并所以树链本身不提供复杂度。
初步判定最后的时间复杂度应该是 \(O(n \log^2 n)\)。

树套树。外层是值，内层是位置。
那么空间复杂度判断为 \(O(n \log n)\)。
考虑我们查询的时候类似于二分答案，在外层树上查询。
因此，对于内层树，我们需要维护以下信息：

要求空间与有权点数成线性，时间不超过 \(O(\log n)\)。

这个自然是喜闻乐见的。
我们进行树上差分。将问题变成子树加，单点求值。
平衡树维护连续段，即可满足上述需求。

复杂度达成。
恭喜你收获巨大难打的待修线段树套平衡树维护连续段。

当然，把内层树改成线段树也可，但是空间会多一个 \(\log n\)。

还是上述问题。考虑改成分治。
显然，外层树就是个整体二分。
内层树是个喜闻乐见的虚树。
做完了。时间不变，空间线性。

整体二分套虚树前缀和。事实上我之前是打过类似的东西的。
提交记录。可以留意一下代码长度。
如果这是正式比赛那么最好注意一点了。

从拿到题到想到上述两个做法其实只需要 5min ~ 10min。
另外，我们暂时可以发现。

权值线段树 -> 整体二分。
序列线段树 -> CDQ 分治。
维护连续段 -> 虚树。

再来一个？

题意转化完是板子。

首先是统计每个人做组长所能统治的人数。
这部分自行考虑。与主题无关。

接下来问题直接变成，区间 \([l, r]\) 内地位高于某个值的最大权值。
静态二维偏序。初步判断时间复杂度为 \(O(n \log n)\)。

由于区间最小值不可容斥，因此改成前缀最小值会更好处理一些。
因此，外层维护下标，内层维护地位值。
内层按照地位值从大到小排序，做前缀 \(\min\)。
发现内层需要二分。
不用分散层叠了，直接类划分树结构即可。

复杂度达成。时空同阶。

当然，就想外层维护权值内层维护位置也可。
把前缀 \(\min\) 改成线性 RMQ 就行了。
（真的有人会这么干吗）

转分治？
还是 CDQ，配上有序分裂 + 前缀 \(\min\) 即可。
这个自然是没什么难度的。

思考时间预计在 3min ~ 5min 之间。
相对来说这个题会好打一点。

鉴定为代码时间换思考时间。
这类东西基本上都有不动脑子的做法。
然而，你们 OI 就是喜欢考板子是吧。
（点名某些大型比赛）

今天本来看到了上面那个 CTSC 题，发现是个板子，准备打。
然后就胡出来一个树套树。
不甘心，转分治，更难打了。
索性跑路了。

这种只会胡题不会打题的毛病还没改啊。。。

你们 OI 什么时候才能扔掉 DS，多考点 ad-hoc 啊。