Ynoi 做题记录 III
标签：扫描线
其实挺套路的。
我们首先考虑设当前的询问是 $x$，然后考虑 $O(nm)$ 的暴力 DP。
发现式子是：
然后我们考虑怎么算这个东西。
我们考虑建一个森林。对于每一个原树的状态，只对所有满足 $f_u \ge 0$ 的点连一条连向原树上父亲的边，那么就能得到一个森林。显然我们只会不断加边。
然后我们意识到如果我们对这个森林跑刚才的 DPair，只需要这样：
注意到这个式子就是加上 $x$ 之后的子树和，其实就是这个子树不加 $x$ 的子树和加上 $x$ 乘上子树大小。那么我们只要能够对于每一个 $x$ 快速求出子树形态，基本上就能快速处理这个东西了。
然后我们考虑把 $x$ 递增排序，那么显然 $f_u$ 也是单调递增的。
因此对于每一个点 $\max(f_v, 0)$ 是取 $f_v$ 还是 $0$ 显然只会变化一次。
因此每一条边只会从 断 变成 连 一次，只要能够快速找到所有这样的边即可。
考虑维护一个 std::set，每一个点对应一个权值 $val$ 表示 $x\ge val$ 时这个点是取 $f_u$ 的，
然后考虑这个 $val$ 是什么，我们显然可以列一个方程：
因此
其中 $sz, sum$ 分别表示子树大小和子树和。
考虑我们每连一条边，都只会改变集合中 $\mathcal{O}(1)$ 个元素的这两个值，而且在原树上相当于一个链修改。
因此我们再加上一个单点修改区间查询的数据结构就行了。
得到复杂度 $\mathcal{O}((n+m)\log n)$。
有没有更优做法我就不知道了，但我确实是压线过去的。
标签：大屑题，垃圾题，傻逼题，Ynoi 之耻
出题人题解.jpg
首先看到二元组想到二离，可以转化为一个 $O(n)$ 次修改 $O(n\sqrt{m})$ 次查询的问题。
修改方式是向集合中插入一个点，查询方式是给出一个数 $x$ 和一个固定的常数 $y$ ，求集合内有多少个数 $z$ 满足 $z \oplus x \le y$。
考虑对 $z$ 建 Trie ，按 $x, y$ 的当前位进行讨论。
具体讨论不展开了，反正一定是 “对一棵子树累加贡献然后进入另一棵子树” 的形式。
然后考虑把 $k$ 层决策压成一层，那么如果能做到每一层 $O(1)$ 查询，一次查询就是 $O(\frac{\log n}{k})$ 的。
然后考虑修改部分，我们对于每 $k$ 层直接枚举 $x, y$ 在这几位的的 $2^k$ 种可能性 ，因此取 $k= \frac{\log n}{2}$ 即可得到 $O(\sqrt{n})-O(1)$ 的一个结构。
然后就做完了，大水题，又水又垃圾。
标签：计算几何
第臭名昭著分块的严格弱化版
考虑一般性的最大子段和做法，显然这里不能动态 dp
因此考虑用前缀和后缀和区间最大子段和那一套来做
显然这里是一个函数的形式，相当于这三个信息是三个分段函数
考虑都是 $f(x)=kx+b$ 的形式，然后每一次 $x$ 不同
因此套用斜率优化那一套理论，建立形如 $(k,b)$ 的一些点。
考虑合并，显然除了 $m=\max\{l, r\}$ 这一部分剩下的都可以直接取 $\max$。
考虑这一部分是形如 $g(x_1+x_2)=f_1(x_1)+f_2(_2)$ 的形式，因此直接闵可夫斯基和就行。
然后考虑询问离线，那么就有单调性了。
因此最终时空复杂度 $\mathcal{O}(n\log n)$。
然后 lxl 这个毒瘤又卡空间。。。
把序列分成 $\mathcal{O}(\frac{n}{\log n})$ 大小的块然后逐块处理即可，虽然我觉得意义不明。
标签：淀粉质
高质量好题，也充分证明了 DPair 是个憨批。
首先我们不难发现，要求的东西可以转化为 “从 $x$ 出发只经过 $[l,r]$ 间的点数颜色”。
那么我们已经有了一个 $\mathcal{O}(n^2)$ 的暴力了，考虑优化。
我们不难发现（指这个 DPair 完全没有意识到）这个以 $x$ 为根可以换为对应连通块中的任意一个点。
然后考虑一个特殊情况，假设所有 $x$ 都为 $1$。
此时注意到我们只需要扫一次整棵树，对于每一个点维护出一个二元组 $(l, r)$ 表示从根到这个点点权的最小/最大值，发现问题转化为了一个可以直接扫描线处理的问题。
那么思路就比较明确了，我们要尽可能使得我们扫描的总点数是有限的。
然后我们又注意到每一个点都有可能作为根，因此降低扫描次数行不通。
我们只能降低所有扫描点数的总和，这使得我们想到点分治。
我们得证明对于任意一个连通块，一定存在一个完全包含当前连通块的点分子树，使得其点分中心在这个连通块内。
其实很显然，我们考虑从点分树的根往下走，显然如果已经包含那么就可以直接选它作为点分中心，否则由于在实际的树中，各个子树都需要经过点分中心才能连通，不经过点分中心后显然与除对应子树外的子树都没有关系。
那么把对应的询问挂在每一个点上，然后对于点分中心直接遍历整棵子树，取出所有合法的询问后暴力扫描线即可。
复杂度 $\mathcal{O}(n\log^2 n+q\log n)$。
以下咕咕咕
标签：构造？交互？
考虑我们其实就是要设计一个数据结构，使得它恰好覆盖某段区间且支持单点插入。
然后它要保证 Worst Case，说人话就是跑的最慢的一组不能很慢。
还注意到它不支持快速合并。
因此我们毙掉了所有均摊复杂度的数据结构，所有需要快速合并的数据结构。
（lxl：这个就是对应 worst case 的带插入区间kth的那个外层平衡树）
注意到查询的时候访问的结点数允许达到 $256$，因此想想它是不是会有地方不平衡。
我们这么设计：
首先考虑它要支持的是覆盖区间，因此默认它是一个 leafy 结构，具体是 WBLT 还是 dpairlist 什么的再说。
我们暂时假装这个结构是个线段树，那么每一次插入基本上就是 $\mathcal{O}(\log n)$ 级别的，但是有一个问题就是某一个结点内元素过多时要分裂。
我们注意到我们一般均摊的方法都是把后面一次特别久的修改所多花的时间用前面少花的时间去替代。
但是我们这里不能直接均摊复杂度，因此我们要考虑用某种方式，来直接均摊每一次的操作数量。
换言之，对于某一次未来的操作，我们要提前把它给处理掉一部分，这样未来做那一次操作的时候就不至于耗时太久。
这里的这个操作显然就是对于插入过多的结点的分裂操作，我们发现它应该是每 $\mathcal{O}(len)$ 次插入就话费 $\mathcal{O}(len)$ 的代价去重构，因此均摊复杂度是对的。
考虑均摊其操作，假设一个结点长度的上界是 $2u$ 而原长是 $u$，我们可以考虑在它长度为 $1.5u$ 的时候每一次新的操作修改它本身和它未来的左右儿子。
这样就能摊掉一些操作了，这样可能会有
咕咕咕咕咕咕