Ynoi 做题记录 II
21、P6105 [Ynoi2010] y-fast trie
标签：STL、小力分讨、平衡树
AFO之后发现自己完全不会数据结构了。。。
首先显然我们可以把每一个数都对 $C$ 取模，然后把集合变成一个可重集，这里比较建议用 std :: map 来实现。
然后显然问题被分成了两部分，一部分是 $x + y \ge C$ ，一部分是 $x + y < C$ （懂我意思吧）。
前一部分，我们显然取最大值和次大值最优，这个应该不需要多解释。
那么就看两数之和小于 $C$ 的部分，然后与第一部分取个 max 即可。
首先我们称一个数的 “最优匹配数”，为集合中与它之和小于 $C$ 且最大的那一个数。称一对互为 “最优匹配数” 的数为一个 “最优匹配”，其权值为两数之和。
那么显然对于一个数，我们要存它在集合中的出现次数，然后我们就可以利用这一部分数据和二分（或lower_bound） 求出它的最优匹配了，这里是 $O(\log n)$ 的，这个可以用 map 实现。
并且我们要实时知道该序列最优的“最优匹配”的权值，于是我们再开一个 map 维护所有“最优匹配”，这里只维护权值即可，不需要维护具体数字，原因与后面的实现有关。
那么我们现在就要考虑怎么维护这两个东西。
首先第一个很好维护，有手就行。
考虑怎么实时维护出所有 “最优匹配” 。
但注意到我们实际只有最大值正确这一个要求，所以我们只需要考虑怎样维护能够保证最大值一定出现且不出现的一定不会出现。
一种很 naive 的想法是每一次插入的时候顺带着插入这个数所对应的“最优匹配”，但是删除的时候显然会炸掉。
所以我们要考虑怎样使得一个数最多被使用一次。
那么这一次显然要是最优的。
也就是说，不优的那一次要被我们剔除在外，不作保存，等删除的时候再恢复回来。
于是我们有了这道题的一个大体思路。
那么我们来考虑一下对于一个数怎样才是更优的，并且这个不优解还能恢复回来。
首先假设我们插入的是 $x$ ，搜到它的“最优匹配数”是 $b$ 。
然而此时 $x$ 还没被插入进去，所以我们再搜 $b$ ，搜出最优匹配是 $c$ （注意大小写）。
当然由于这是个可重集， $c=x$ 可能成立，这里不去考虑。
显然若 $c \ge x$ ， $x$ 不可能进入最优匹配，故直接退出。
接下来考虑 $c < x$ 的情况。
那么显然我们可以考虑把 $(x, b)$ 加进去了，但是删不删 $(b, c)$ 还得讨论 $(b, c)$ 在不在集合内。
于是我们搜一下 $c$ 的最优匹配 $d$ ，判断 $b=d$ 是否成立即可判断 $(b, c)$ 是否在集合内了。
删除其实同理，我们只需要把原来的插入转化为删除，然后假装我们要插入，看看会发生什么变化，然后把这些变化一一撤销即可。
于是就做完了，复杂度为大常数的 $O(n\log n)$
标签：珂朵莉树、复杂度分析、二维数点、CDQ分治
首先我们考虑单点修改区间数颜色怎么做。
不要跟我说什么带修莫队。
有一个十分金典经典的套路是记录每一个元素本身以及它的同色前驱的位置，转化为一个二维数点，前驱不在区间内且本身在区间内的点可以产生 $1$ 的贡献，这个用 CDQ分治然后差分一下什么的就行了（没想到吧这是我第一次用CDQ分治二维数点）。
考虑单点修改，我们修改这个位置的前驱，前驱的后继，后继的前驱就行了，然后可以通过加一维时间以及负权点来实现修改。
突然感觉 CDQ 有点强大的啊。
然后我们考虑区间修改。
区间推平？我会暴力珂朵莉树！
如果你是暴力数颜色的话，你就只能拿 $10\text{pts}$ 。
我们考虑把两种方法结合起来。
这时候有人要问了，这样子的话修改的点数难道不是 $O(nm)$ 的吗？
考虑对于一次推平，我们在珂朵莉树上的操作是删除一堆同色区间然后插入一个大同色区间，不难发现一个同色中只有 $l$ 结点的位置的前驱不是它本身的“位置 - 1”。
于是我们删除的这些小区间中，我们只需要修改每一个小区间的 $l$ 结点即可！
显然我们每修改一个 $l$ ，小区间就减少一个，而且由于一个小区间同色，需要修改的“前驱的后继”和“后继的前驱”也都只有一个，而且事实上这里同样用 std :: set 维护的话对于每一种颜色可以方便地求出后继，也就是说直接修改后继就行了。
所以每一个区间产生的贡献是 $O(1)$ 的，于是暴力修改的点数变化量是 $O(n+m)$ 。
那么就转化成了若干单点修改和矩形查询，CDQ分治二维数点即可。
本题 $n, m$ 同阶，所以最终复杂度 $O(n\log^2 n)$ 。
标签：扩展欧拉定理
这道题对数据结构要求为 $0$ 。。。
首先连续取幂考虑扩展欧拉定理。
可以直接理解为
然后不难发现每一次取 $\phi()$ 都至少减少二分之一。
所以可以直接暴力，从 $[l, r]$ 开始递归处理，那么我们需要做的就是判断 $f(l + 1, r)$ 是否 $\ge \phi(m)$ 。
显然若出现 $1$ 则可以直接返回。
若没有 $1$ ，则往后 $5$ 个以内必然超过 $\phi(m)$ ，因为 $2^{2^{2^{2^2}}}$ 是很大的（自己算算）。
所以往后判断 $5$ 个就可以得到是否取模，而且不难发现，不取模的情况下后面有效数字必然 $< 5$ 个，可以直接暴力，否则递归下来也就最多 $\log$ 层。
可能还有一些实现上的细节。
树状数组沦为工具人。
复杂度 $O(n\log^2 n)$ ，我们假装 $n, p$ 同阶好了。
真要说的话似乎是 $O(n\log n(\log p+\log n))$ ？算了算了当同阶吧（（
24、P6019 [Ynoi2010] Brodal queue
标签：分块
区间推平区间相等二元组对数。
首先我们考虑区间相等的二元组的对数若没有修改怎么求。
莫队太没前途了，我们考虑分块。
一种分块的思路是最基础的在线化莫队，即记录任意两块之间的答案，然后向两边扩展，但这显然不好修改。
所以我们要考虑如何维护容易修改的信息。
不难发现，一般来说前缀和比较好维护，因为我们原先难以维护的原因在于要修改 所有包含某一个块 的 块构成的区间 ，而这一部分复杂度是比较大的，这时的均摊就是要带一个 $n^\frac{2}{3}$ 的复杂度（即带修莫队）。
而前缀和修改一个后缀就行了，复杂度是 $n^{1\over 2}$ ，比较优秀。
然后考虑把这道题转化为前缀和怎么搞。
我们先考虑单点修改。
不难发现我们散块是很好处理的，所以接下来所有东西 都以块为单位 。
首先二元组对数即 ：
（ cnt[x] 表示区间内 x 的个数）
这个东西显然可以转化成：
自证不难
那么我们维护这个式子即可：
这样一来就阳间多了。
接下来我们考虑用一个前缀和之差的形式表示这个值。
显然为 ：
（ b 表示前缀和）
于是我们需要维护一个前缀和的平方。
不难发现这很容易做到，并且这东西对于每一个 $x$ 互相独立，故可以 直接维护其和，设为 $s[]$ 数组。
然后我们就只需要维护 $-2b[r]b[l-1]$ 这个东西就行了。
不妨设 $f(i, j)=\sum_{x} b[i]b[j]$
那么我们考虑怎么维护这个东西。
不难发现，当一个块 $k$ 被修改时，会出现三类 $(i, j)$，我们假设 $k$ 内的 $x$ 被修改了 $y$ ，并且这一部分允许 $O(\sqrt{n})$ 的复杂度。
我们不妨设 $b[i], b[j]$ 均对于 $x$。
- $i < k, j < k$ 显然没必要动。
- $i < k, j\ge k$ 这一部分的修改量为 $b[i](b[j]+y)-b[i]b[j]=b[i]y$ ，故枚举 $i$ 然后用差分的思想修改即可，因为我们查询时显然也可以带 $\sqrt{n}$。
- $i \ge k, j \ge k$ 这一部分的修改量为 $(b[i]+y)(b[j]+y)-b[i][j]=b[i]y+b[j]y+y^2$ ，同理修改即可，不做赘述。
然后查询就十分方便了，先整块直接用 $f, s$ 两个东西算出来，然后散块暴力就行了。
然后是区间推平。
我们可以每一个块打一个 $tag$ 表示是否被整块推平，那么整块推有 $tag$ 的块时就是修改次数就是 $O(1)$ 的，因为不难发现我们上述单点修改适用于一个块内多个 同色元素 被 同时修改 的情况。
然后散块的话我们可以考虑对 每一种颜色 暴力修改，因为这样的话修改次数就是区间内的颜色数，而扫描散块的复杂度显然是 $O(\sqrt{n})$ 所以不需要过多考虑。
那么我们每一次修改最多增加 $O(1)$ 个无 $tag$ 的块，并且这里面的颜色数是极其有限的，最终复杂度是正确的。
然后我们处理整块的时候，无 $tag$ 的块显然可以暴力处理，这里的复杂度正确性上面已经说过，有 $tag$ 的块无需修改直接 $O(1)$ 打 $tag$ 即可，在询问的时候当作 一次性加入多个相同的数 处理即可，不然会导致复杂度错误。
最后复杂度 $O((n+m)\sqrt{n})$ ，空间复杂度 $O(n\sqrt{n})$ 。
标签：polylogの分块、空间の优化、空间卡常
首先这东西咋看之下像是一个第二分块。
然后一看值域人傻了，发现这不是第二分块的做法能承受的值域。
所以我们考虑一个 与值域无关 或 log值域 的做法，本题是后者。
这题不难发现是一复杂度分析的题目，我们考虑怎样使得它的复杂度正确。
首先有一种 naive 的想法就是对值域分块，假设 块数 为 $B$ 。每一个块开一棵 序列线段树 ，每一个结点记录一个区间内的 $\max, \min, \sum$ 还有出现的数的个数，显然这些信息可以 $O(B\log n)$ 查询并合并得到。
然后每一次修改，我们考虑会出现 值域块之间数值的移动 ，每一个值会至少移动 $O(B)$ 次，所以均摊下来就是 $O(Bn)$ 次查找。由于我们在线段树上修改，我们 每次 找一个数的复杂度应该是 $O(\log n)$ ，所以 块间移动 这部分的总复杂度是 $O(Bn\log n)$ 的。
但是这有一个前提，那就是我们找一个数的时候要能够 准确找到所有会被移动的数 ，即我们不会在线段树上往下查询到一定深度了，才发现这个区间里没有会被移动的数。
然而我们不可能详细记录区间信息，我们还是只记录 $\min, \max$ ，现在就是要求我们通过这两个信息判断一个结点内是否有需要被修改的数。
这里我们可以分类讨论，首先假设我们修改的是 $x$，当前结点是 $\min = l, \max = r$ （注意这里是最大值最小值）。
我们显然可以分三类：
- $x \ge r$ 显然对于这一个区间什么都不会发生，直接退出。
- $x < l$ 这里我们显然只需要考虑 $l$ 是否会掉到其他的块里面。如果会，那么就暴力往下遍历，不难发现这样一定会最终遍历到需要 块间移动 的位置；如果不会，我们就给这个区间打上一个区间减的 $tag$ 就行了。
- $x \in [l, r)$ 这里就比较难办了，不难发现 $[l, x]$ 之间的数并不会发生改变，而且仅凭一个 $r$ 并不能完全判断这个区间中是否有会掉到其他块内去的数，因为可能 $r$ 并不会掉到其他块中，但存在一个 $(x, r)$ 之间的数会掉到下一个块中，而且这样的数是否存在我们并不知道。
那么我们考虑怎么处理 $3$ 问题，我们回头看看，我们有什么地方还有改动的空间呢？
不难发现我们还没有定块长，而且这道题的复杂度似乎和块长没有关系，故 块数越少越好 。
并且，我们需要使得 $3$ 情况可以被判断，一个有效的思路是 一旦 $x \in [l, r)$ 成立，那么这个块一定需要被修改 。
即我们需要满足 $r-x<l$ 对 同一块内 一切 $(l, r)$ 的二元组成立。
不难发现 $r < l + x$ ，故 $r_{\max}=l+x-1$ ，又因为我们要保证这个式子对于任意 $x\in [l, r)$ 成立，故取最劣情况 $x=l$ 即 $r_{\max}=2l-1$ 。由于我们要使得块数尽可能少，我们取 $r=r_{\max}=2l-1$ 。
所以我们进行的就是类似 倍增 的 不均匀分块 ，这个思路是真的妙。
不难发现块数 $B= \log V$ （ $V$ 为值域），所以总复杂度为 $O((n+m)\log n\log V)$ ，空间复杂度 $O(n\log V)$ 。
没错，一道分块题拥有了 polylog 的复杂度，没想到吧（（
但是赛后 lxl 卡空间了。。。毒瘤石锤了。
我们发现空间会炸的原因在于 $B$ 比较大，所以我们不得不把 $B$ 变小。
但是根据刚才的分析，这不已经是 $B$ 的最小值了吗？
此时就需要我们牺牲时间换空间了。
不难发现，我们之前讨论 $3$ 情况时直接钦定了 $r < l + x$ ，因为这样 $r$ 不会被多算。
那么，如果我们允许多算呢？
不难发现，若 $r \ge l + x$ ，那么每一次 多算 $r$ 都会产生 $O(\log n)$ 的复杂度。
但是不难发现，每一次 多算 ，$r$ 都会减少 $x$ ，而 $x$ 至少也是 $l$ 。
所以我们假设 $r < bl$ 即取 $r=bl-1$ ，此时 $B=\log_b V$ ，空间得到了优化。但是时间上要多一个 $O(b)$ 的常数，不过同样的我们可以少跳几次，故时空复杂度分别为 $O(Bb(n+m)\log n)$ ，$O(Bn)$ 。
简单算一算就会发现 $b=8$ 比较合适，时间退化不是很大的情况下把空间缩小到了原来的 $1\over 3$ 的样子。
但是这么一算还是要 $500 \text{MB}$ 的样子，不太行。
不过我们意识到我们用的数据结构是线段树，我们可以采取 小于某个阈值即暴力 的操作手段来进行空间优化，具体来说就是一个叶子结点表示的是一段长度为一个阈值 $k$ 的区间而非一个长度为 $1$ 的区间。
不难发现，$k$ 每扩大一倍，总空间就缩小一半（因为叶子结点被删没了，故一半结点没了），故 $k$ 足够大时空间会大大缩小。
发现 $k=16=2^4$ 时，总空间也除以 $16$ ，然后就没什么问题了。而且由于本来线段树跑最后几层也需要一定的常数，故时间上退化不会非常严重。
然而实测 $k=32$ 时效率更高（（
另外，如果使用动态开点的话，可能还要多维护一下左右儿子的标号，所以本题中对空间优化意义不大，故不选用。
这东西复杂度算起来感觉会非常屎，就当是个优化吧（（
据说叫什么 “底层分块” ？
标签：分块
比较简单的一道分块题。
感觉和 P3203 [HNOI2010]弹飞绵羊 有点像。
首先考虑一遍所有 polylog 或更低的求 LCA 的方法，发现在这道题好像都用不出来，于是考虑根号做法。
我们对序列分块。
为了使得我们能够快速查询，我们在查询 LCA 时每一步都要 跳至少一个块，故考虑维护每一个点 出块 后的第一个祖先和真实的祖先。
假设某一个块内所有点出块后的第一个祖先就是真实的祖先，由于祖先 只减不加，故后面所有状态这个块内的祖先 全部出块，因此我们维护时直接打 tag 即可，每一个块 $O(1)$ 。
并且不难发现每个块被修改至多 $\sqrt{n}$ 次之后必然会达到全部出块的状态。
因此，这 $\sqrt{n}$ 次修改允许 $O(\sqrt{n})$ 的复杂度，即重构。
重构的时候扫一遍这个块，然后每一个点向前连，用类似路径压缩的方法处理即可，十分简单。
故修改复杂度 $O(n\sqrt{n})$ 。
然后找 LCA 的话就用类似倍增的方法暴力跳。这里对于全部出块的块很好处理，但是对于没有全部出块的块可能会出现两点虽然在同一块内，但是其 LCA 不在这一块内的情况，只维护刚才的东西难以在块内判断 LCA 是否在这个块中。
不难发现我们可以在每一次重构的时候顺便维护出每一个元素 块内最前面的祖先 ，用类似并查集的思路，判断一下这一个是否相同即可，显然这个东西只会在 没有全部出块 的块内被用到，而且每一次重构显然可以顺便求出，故不会改变复杂度。
最后状态显然为两个元素的 LCA 在某一个块内，这一部分暴力扫即可。
故询问复杂度 $O(n\sqrt{n})$ 。
总时间复杂度 $O(n\sqrt{n})$ ，空间复杂度 $O(n)$ ，可以通过本题，完全不卡常。
27、P6018 [Ynoi2010] Fusion tree
标签：Trie
首先有一个极其简单的套路：对于这种距离为 $1$ 的询问，我们可以考虑单独维护父亲，然后对于所有儿子来一个全局修改全局查询的数据结构。
这里我们使用的就是 Trie 。
我们现在要支持的就是一个 全局+1，单点修改，全局查询异或和 的一棵 Trie 。
不难发现两个性质：
- 我们这里由于全部都是全局查询，故不关心数值的具体大小关系。
- 我们全部都是全局修改，并且全局加 $1$ 本质上就是把所有最低位为 $1$ 的数，往上加。
那么我们就可以考虑这样一个事情，我们建一棵 自下而上 的 Trie ，即从低位向高位建 Trie 这样就可以方便地实现加 $1$ 的操作，因为我们显然可以通过 $0$ 变 $1$ ，然后 $1$ 变 $0$ ，之后递归 $1$ 的操作来完成一次 $+1$ ，并且复杂度是 $O(\log V)$ 的。
这样子的优势在于，我们原本的建 Trie 方式会使得有大量的最低位需要被修改，现在每一位都只会修改一次，故达到了极大的优化。而且由于这道题不关心具体大小关系的性质，这么做是对的。
显然这样我们可以方便地维护出每一个位置的异或和，也可以方便地单点修改。
然后父亲什么的特判一下就行了，至于单点的权值查询什么的打个 tag 就解决了。
复杂度 $O((m+n)\log V)$ ，十分优秀。
标签：线段树、最优化
可能是这一阶段的最后一道额外练习的数据结构了，题目名称十分应景。
首先我们发现这个 $n$ 和这个 $m$ 的范围有一定差距，大胆猜想这道题需要 $O(n\log n)$ 预处理 $O(m\log^2 n)$ 查询。然后你会发现事实就是这样
不过这对我们解题似乎没有什么帮助。
于是我们还是数据结构题的经典思路，考虑我们要维护什么东西。
我们可以这样想：
我们一段区间的区间和我们是知道的，然后这段区间的答案显然可以表示成 原先的区间和减去取模数的一个倍数 的形式。
那么我们看看这个 倍数 能不能被维护出来，不难发现这个东西的实际意义就是 取模几次 即 有几次当前数出现 $\ge p$ 的情况 。
不难发现，对于某一段区间 $[l, r]$ 这东西只会受到我们在 $[l, r]$ 之前的 当前数 的影响，并且这个次数不会大于区间长度。
而且显然，这个次数的值随着 当前数 的增加而 单调递增 ，证明略。
那么这启示我们可以对于线段树上每一个结点开一个 std :: vector ，用来表示 扫过这段区间后次数为某数所需要的最小数 ，在查询的时候二分一下就可以判断出这个区间对于任意当前数的次数。
这部分是 $O(m\log^2 n)$ 的，然后我们考虑怎么合并两个 vector 。
首先我们不难发现合并之后这个 vector 还是递增的，于是我们可以 $O(len^2)$ 扫描左右儿子来处理出最优方案，这里的最优方案即上文提到的 最小数 。
这东西显然是单调的，即对于一组 $l[i], r[j]$ ，它对 $rt[i+j]$ 的贡献显然优于 $l[i+1], r[j-1]$ 的贡献，所以可以 $O(len)$ 双指针直接搞定。
好吧半年后再看发现不是那么显然。
如果不严谨证明的话，只需要考虑每一次 $x$ 变化都一定是把一个 $\le 0$ 的数填到 $p$ 为止，这样得到 $rt[x] + p \le rt[x + 1]$，然后带入式子就会发现上面那个结论成立。
严谨一点可以这样：
我们考虑找出 $rt[x] + p - 1$，证明这个数丢进去不会超过 $x$ 次即可。
考虑它第一次把某一个不减 $p$ 的位置变成减 $p$ 的，此时这个位置的值一定是原先运行到这个位置时 $-1$。
注意到最后一个被减的位置后面的位置一定都是 $\le 0$ 的，不然减去某个后面出现过的 $> 0$ 的数后，前面要么会少减一次，此时后面一定还能再减；要么干脆就不会少减，此时也不影响。
总而言之这个最后一次的位置还能后移，这与定义矛盾。
再考虑 $rt[x]$ 的定义，不难得到在这个 “无中生有” 的位置一旦减 $1$，其后面原本减 $p$ 的位置必然要减少一个。不然我可以取 $rt[x]-1$，要么是运行到这个位置且后面不变，要么干脆前面反而多了一个，那么我就可以从后面拿一个 $p$ 到前面来又更优。
总而言之也与定义矛盾。
证完之后就好做了，判一下一组 $i, j$ 指针是否合法即可，即通过前者能否到达后者，这个容易判断不作赘述。
所以最终时间复杂度 $O(n\log n + m\log^2 n)$ ，空间复杂度 $O(n\log n)$ ，还有几个小优化，随便加一加就拿最优解了，不赘述。
标签：分散层叠算法、分块
$\color{red}{「？？？？第十分块」}$
首先我们看到这种 “最大值小于” 的问题，不难想到我们要求的就是和 “全部元素小于给定数的极长连续段” 有关的一些信息。
所以我们要维护这些连续段，考虑对序列分块，块长为 $b$ ，我们不妨设 $> x$ 的数为 $1$ , $\le x$ 的数为 $0$ ，那么我们得到的就是一个 $01$ 序列。我们要求的就是每一块的 块内答案、块的最长全 0 前缀和块的最长全 0 后缀 的长度。
但是对于不同的 $x$ ，这个序列不同。
不过显然对于某一个块，不同的块内信息最多 $O(b)$ 种，并且每一种对应一个 $x$ 的连续段，不难想到我们可以二分。
然后我们发现，这东西显然可以方便地重构，一次重构也是 $O(b)$ 的。
散块查询显然是 $O(b)$ 的，但是整块需要二分的话查询复杂度为 $O({n\over b}\log b)$ ，这是我们所不能接受的。
我们使用分散层叠算法在线段树上的应用（其实哪怕不知道这个东西往下看也能看懂），即先对于所有 块 建立线段树，每一个结点维护一个 有序序列 便于二分，其中所有叶子结点（即我们分好的块）维护的就是块内的元素 带信息排序 后的结果。
然后对于每一个父亲结点，维护的信息为两个儿子的序列 每隔 p 个取出一个后形成的序列 归并排序后的结果，并且对于每一个位置维护其在两个儿子中对应的后继。这里 $p$ 是一个我们自由选取的阈值。
举个例子，假设
那么
其中 $1, 6$ 来自第一个序列， $3, 12$ 来自第二个序列。
这样子的话，我们在区间查询的时候可以对于这一个区间的根结点二分，然后得到两个儿子中的后继，不难发现这里得到的后继与 $x$ 在其儿子中的真实后继差距不超过 $p$ ，这部分暴力即可。由于 $p$ 是常数，复杂度 $O(1)$ 。
然后线段树结点个数为 $O({n\over b})$ ，故一次查询的复杂度变为 $O(\log {n\over b} \log b+{n\over b})$ 。
取 $b=\sqrt{n}$ 得到复杂度 $O(n\sqrt{n})$ 。
最后我们不难发现这个算法可以应对更大的值域，并且做到了强制在线，而且可以利用在线段树上打 tag 的方式实现区间加，这里不多赘述了。
标签：线段树、分块
一道有手就行的 Ynoi 。
首先我们不难发现对于一次修改，所有 长度相同 的线段树结点的修改量 基本相同 。
而且对于这个 区间加区间rank 的问题，我们一直以来有一个不错的分块解法，即整块二分，最终复杂度 $O(n\sqrt{n\log n})$ 。
然后我们打表不难发现，一棵线段树上长度本质不同的结点最多 $O(\log n)$ 种，而且这些结点的长度是 $2$ 倍 $2$ 倍增长的。
因此我们对于每一种长度的结点分块，然后每一次该怎么做怎么做，最终复杂度是 $T(n)=T(n / 2) + O(n\sqrt{n\log n})$ ，即 $O(n\sqrt{n\log n})$ 。
然后这东西用分散层叠可以优化到 $O(n\sqrt{n})$ ，但没必要。
31、P5528 [Ynoi2012] WC, THUWC, CTSC 与 APIO2017
标签：分块，根号分治，定期重构
一道我做了一个下午 + 晚上的大水题，我还是太菜了。
首先这种 所有模几为几 的东西大概率根号分治。
一种想法是树分块，但这东西不仅想起来屎还写起来屎， 应该 被果断弃掉（没错我坚持树分块坚持了一个下午）。
然后我们考虑这样一个事情，我们对于所有 $x > \sqrt{n}$ 的询问可以直接暴跳 深度 ，但是对于不同的深度我们只取该深度中的一部分修改，我们需要处理这一部分。
一种思路是 dfs 序，但是很不方便，我们考虑 直接扫 。
但是复杂度显然会炸，因此我们考虑每 $\sqrt{n}$ 个修改定期重构一次，不难发现这里重构一次是 $O(n)$ 的，并且我们扫整棵树的时候所有存下来的修改都可以直接暴跳啥事儿没有。
然后我们每一次询问额外搜一下最近的几次修改就行了，显然这部分复杂度也是 $O(\sqrt{n})$ 的。
然后是 $< \sqrt{n}$ 的做法，这一部分的一个经典套路就是直接存，因此我们考虑对树分块（注意这里不是一般意义上的树分块），每一个块开一个 $O(\sqrt{n}\times \sqrt{n})=O(n)$ 的数组 $f_{i, j}$ 表示 深度在模 i 意义下为 j 的点被加了多少 。
然后我们一次修改显然只会对每一个块进行 $O(1)$ 次修改，然后散块暴力即可。
显然这里直接对 dfs 序分块啥事儿没有，然而 DPair 这个 shabi 胡了一下午树分块。
最终各部分复杂度 $O(n\sqrt{n})$ 空间复杂度也是 $O(n\sqrt{n})$ ，可能略卡常，把重构的 dfs 改成迭代会快很多。
标签：莫队、bitset、阈值分治
人傻了，这道题不卡常，问题是我写挂了 INF 发（（（
其实是一道不难的题。
首先我们不难发现，我们要求的这个东西有点像把值域分成若干个大小为 $b$ 的块，然后考虑一个最长的块的前缀使得这些块内元素有交。
集合有交不难想到用 bitset 去处理，那么问题转化为把 bitset 分成若干个长度为 $b$ 的段，求一个最长的段的前缀使得这些段与起来不为 $0$ 。
但是我们需要把 bitset 分成若干个长度为 $b$ 的段，这个用传统的 std :: bitset 实现不了，考虑手写，那么用类似分块的方法可以做到每一次询问 $O({V\over w})$ ，其中 $V$ 是值域。
然后这个 bitset 内容的 维护 可以用莫队处理。
不过对于 $b \le w$ 的询问， bitset 难以完全发挥优化效果，即我们手写的 bitset 压不了位。比如 $b=1$ 时 bitset 会退化到 $O(V)$ ，因此我们考虑对于这部分另外处理。
不难发现这部分数比较少而且比较小，因此我们考虑分开另外处理。
我们对于每一个 $\le w$ 的 $b$ 跑一次莫队（注意块长要变），然后每一 组 询问我们开 $b$ 个 bitset ，令 $t_{i, j}$ 表示模 $b$ 意义下结果为 $i$ 且除以 $b$ 后结果为 $j$ 的数是否存在，然后对于每一个 bitset 求 mex 然后取最大值即可，不难发现这部分的总复杂度仍是 $O({V\over w})$ 。
当然你想直接回滚莫队求 mex 也不是不可以，不过不会优化整体复杂度，没有太大的必要。
但是这部分要求动态的 bitset 空间，故照样要手写 bitset 。
最终如果块长合理的话，复杂度应该是 $O(n\sum \sqrt{m_i} + m{V\over w})$ 。
33、P5065 [Ynoi2014] 不归之人与望眼欲穿的人们
标签：分块、位运算
单点修改全局查询 “区间 or 和 $> x$ 的最短区间长度” 。
拆位拆位拆个 P 的位，一天到晚就只知道拆位，你看现在连道紫题都做不出来了。
首先我们看到位运算不难想到拆位，不过这道题不拆位。
用到一个 or 和的性质：对于一个固定某一端点的区间，其 or 和最多 $O(\log a)$ 种可能性。
这个感性理解一下就行了，我们考虑怎么用这个性质解这道题。
首先我们对序列分块，设块长为 $B$ ，不难发现答案区间要么完全被某一个块包含，要么跨两个块。
先考虑前者的处理，我们对于一个块维护出一个数组 $f$ ，$f_i$ 表示块内长度为 $i$ 的区间最大的 or 和，那么每一个块二分即可。
考虑怎么维护这个东西，由于我们是单点修改，我们可以暴力重构。
考虑利用那个 or 和的性质，不难发现一个块内最多 $O(B\log a)$ 种 or 和，这个量我们是可以接受的，考虑怎么均摊 $O(1)$ 地找到所有的 or 和。
一种直观的想法是用一个类似于子序列自动机的结构，从后往前扫，维护出每一位上的最前出现的位置，显然以当前扫到的这个结点为左端点的区间中，区间 or 和发生改变的位置就是这些，那么用类似差分的思想就可以维护处上文提到的 $f$ 数组了。
但是由于我们要按顺序扫这个子序列自动机，因此它的复杂度要多一个排序的 $O(\log\log a)$ 。
不过不难发现，我们每一次都是把一些原子序列自动机中的位置改成一个当前序列中的最小值，因此可以用归并排序的方法 $O(\log a)$ 单次排序。
于是我们得到了一个 $O(B\log a)$ 的重构方法。
然后考虑跨块的处理。
首先由于这东西跨块，那么我们取的必然是一个块的后缀，一堆整块，加一个块的前缀，不难发现一个前缀 + 一个后缀的 具体位置 可以唯一确定一段区间（废话）。
显然这个后缀和这个前缀本质不同的值也就 $O(\log a)$ 种，因此总共有 $O({n\over B} \log a)$ 个前缀后缀可以扫。
考虑用双指针处理这个问题，复杂度就是前后缀的数量，为 $O({n\over B} \log a)$ 。
取 $B=\sqrt{n}$ 得到复杂度 $O(n\sqrt{n} \log a + n\sqrt{n} \log n)$ 。
标签：树分治、平衡树、扫描线
纪念一道完美踩中我所有数据结构知识盲区的 Ynoi 。
首先对于这种离线的、数个数的问题大概率是使得每一个类只会产生一次贡献，然后用扫描线解决。
考虑如何让一个 “C块” 只产生一次贡献。
我们有一个十分平凡的思路，就是给所有元素一个比较策略，然后每一个类只有最优的那一个产生贡献。
假如我们已经设计出了这个策略，那么我们就可以考虑对于一个元素，如果区间内存在比它更优的元素，那么它就不产生贡献，可以记录最左边比它更优和最右边比它更优的元素分别为 $L_i, R_i$ ，那么就转化成了扫描线的经典问题：“数一个区间 $[l, r]$ 内有多少个元素 $i$ 满足 $L_i < l$ 且 $R_i > r$ ” 。
这个有一个比较简单的解决办法就是把所有询问按右端点排序，然后在序列上维护一个指针从左往右扫。每次扫到一个 $i$ 说明这个 $i$ 可以产生贡献，但是这个贡献会被 $L_i$ 抵消，然后扫到 $R_i$ 时说明对应的 $i$ 再也无法产生贡献。这些显然可以转化为单点修改区间求和，用树状数组就可以解决。
那么接下来考虑如何设计这个比较策略。
首先一个思路是一个 “C块” 中只有最浅的那些点产生贡献，故我们设一个第一关键字为 $dep_i$ 即在原树上的深度，而且这样的一个好处就是如果对于某一个点，没有深度比它更小的与它 “C连通” 的点，那么它一定是当前 “C块” 中深度最小的。
但是这样不一定唯一，于是我们把每一个点的编号当作第二关键字，即我们可以设计一个如下的比较函数：
inline bool cmp(int u, int v) {
return dep[u] < dep[v] || (dep[u] == dep[v] && u < v);
}
考虑为什么不能直接把编号当作第一关键字，这是因为编号这个东西，可能有一个离当前的很远的点更优，但当前点周围的点都更劣，会导致统计多次。
而在只有最浅的一层产生贡献时，不难发现这些点互相 “C连通” ，故这些点中编号最小的点一定是唯一确定的。
最后考虑怎么统计这个东西。
由于我们讨论的是和 “距离为C” 有关的事情，那么我们大可以考虑采用点分治这一类的东西。
我们考虑点分，每一次首先对所有范围内的点排序，然后动态维护一棵平衡树，每一次在平衡树上查询合法的前驱后继即可。
复杂度 $O(n\log^2 n + m\log n)$ 。
另外据说这道题有什么 Top Tree 分治的单 $\log$ 做法，反正我不会。
标签：KDT、分块、扫描线
这都没想到 KDT 我是不是可以退役了
其实应该不难
考虑我们一般的做法，就是每一个 “关键点” 只在最后一次出现的位置产生贡献
那么剩下的部分就是一个扫描线了，考虑现在要处理的就是每一次把一个矩形内所有关键点在原先位置减去，然后在新的位置加上
看起来很不可做，但仔细想想有点像区间推平，因此估计有均摊的做法
考虑直接对关键点建 KDT ，然后每一次就把所有被完全包含的点推平成当前位置，再回收这些点子树内的所有标记即可
不难发现两部分都是 KDT 的复杂度，也就是 $O(\sqrt{n})$ 的
考虑 $n, m$ 同阶，那么后面的 $m$ 全部用 $n$ 代替
那么现在就是 $O(n\sqrt n)$ 次单点修改和 $O(q)$ 次后缀和查询
因此我们摊一下复杂度，使用 $O(1)-O(\sqrt{n})$ 的分块
但是这样后面那一部分复杂度似乎会偏大，众所周知 $10^6$ 过不了 $n\sqrt{n}$
不过我们注意到 KDT 常数也很大，所以某种意义上平衡了复杂度？
其实也可以采用增加分块层数的方法，这样前面会变成常数稍大的 $O(1)$ ，后面可能就是 $O(n^{1\over k})$ 这种东西了，没实现过不知道（（
据说 $O(1)-O(\sqrt{n})$ 就能过
然后考虑实现上的细节
发现那啥如果用类似平衡树的方法建 KDT ，这些 tag 会非常难打
把 KDT 改成 leafytree 的形式，常数应该也不会增加多少，而且处理这种区间问题更为清晰，避免了大量关于当前根结点的分类讨论
标签：数学、推式子
这道题和数据结构基本没有关系
考虑先化一下方差公式：
不难发现由于是子序列，每一个位置的贡献都是相同的，因此前面这一部分可以写作
的形式，因此我们要算这个 $k$
那么考虑枚举长度，然后判断贡献，
后面这个式子太难看了，我们改一改
然后就可以求了
考虑后者的求法，就是给你一个序列，求出每一个子序列的平均数的平方之和
发现对于一个子序列，这玩意儿其实就是
前面一部分略显眼熟，考虑用类似的方法化简
考虑递推， 设
因此这部分的系数就是 ${1\over n} f(n)$ ，预处理即可
然后考虑第二部分
还是考虑枚举，那么就是每次选两个数，由于 $n=1$ 时这个式子显然为 $0$ ，因此从 $2$ 开始枚举，发现每一对数的贡献为：
根据其意义，得到
而后面两个我们都是能求的
然后就做完了
复杂度 $O(n\log n)$
37、P6579 [Ynoi2019] Happy Sugar Life
标签：二离、分块
这题还有个脍炙人口的名字，叫时代的眼泪
考虑这玩意儿严格难于区间逆序对，因此直接想分块就完事儿了
首先无论哪种做法都要对序列分块，因此我们也这么干
但是发现这里不能直接二离，答案维护不得
因此考虑直接在分块上算
首先每一次询问显然传统艺能五部分贡献：整间、散间、整散、散内、整内
考虑散块都好处理，直接利用二离那套理论把散块往对应位置上挂就行了
详细一点，考虑需要处理的其实就这几部分：
左散块内部+左散块与整块-右散块内部-右散块与整块-两个散块之间
其中前两部分可以合并处理，后三部分也可以合并处理
至于 $[1, i-1]\to i$ 的贡献怎么一一处理，考虑用 std::vector 存询问，然后每处理一个弹出然后不断向后跳就行了
然后考虑整块内部，考虑逐块处理，然后最后每个块 $O(m)$ 扫一遍所有询问得出答案
这需要我们 $O(1)$ 查询一些东西，因此要 $O(n)$ 处理出该块所有值域区间的全局答案
考虑先离散化，然后设一个数组 $f[i][j]$ 表示值域离散化后在 $[i, j]$ 间的该块答案
可以用类似二维前缀和的方法 $O(\sqrt{n}^2)=O(n)$ 求出
最后考虑整块间
我们要求的贡献可以看做 $[l, r] \times [l, r]$ 也就是 $([1, r]- [1, l - 1]) \times ([1, r]- [1, l - 1])$
拆开来，就是 $[1, r] \times [1, r] - [1, r] \times [1, l - 1] - [1, l - 1] \times [1, r] + [1, l - 1] \times [1, l - 1]$
再把第二、三项拆成 $([l, r] + [1, l - 1]) \times [1, l - 1] + [1, l - 1] \times ([l, r] + [1, l - 1])$
拆开带回，发现某一项是 $0$ ，因此最后要求的就是 $[1, r] \times [1, r] - [1, l - 1] \times [1, l - 1] - [1, l - 1] \times [l, r]$
前两部分显然是一种求法，后面的是另一种求法
不难发现最后一项由于两个区间不交，显然只与出现次数有关，因此可以在上面求整块内时顺带求出
那么现在相当于要求 $O(n)$ 组形如 $[1, x] \times [1, x]$ 的东西
相当于降了一维了
那么考虑扫描线，从小到大枚举 $x$ 这一维
发现由于是顺序对，只有 $x$ 所在块以及其前面的块会发生答案的改变
我们假设 $g[i][j]$ 表示块 $i$ 与 块 $j$ 此时的答案
那么，每一次修改相当于 $g[1\dots i-1][i]$ 进行修改
然后查询形如 $\sum_i\sum_j g[i][j]$ 的一个东西
考虑这东西是可以前缀和优化的
于是 $O(n\sqrt{n})$ 做完了
标签：dsu on tree，扫描线
这个憨批 DPair 为了抢一血写了一个下午的根号做法然后卡了一个晚上的常，最终在 神·zhoukangyang 秒掉这道题后发现他代码里没分块才觉悟过来有超级 naive 的 polylog 做法
考虑这道题严格难于区间数颜色，因此不是扫描线就是莫队
莫队做法的大常数难以通过本题，因此考虑扫描线
扫描线数颜色的经典套路就是对于每一个颜色维护出其最后一次产生贡献的位置，然后求一个区间和
考虑这道题，不难发现每一个 LCA 可能 会在 后往前第一次 出现的位置上产生贡献
然后我们先考虑求出所有这种位置
发现若一个点要作为 LCA 产生贡献，首先它一定可以在它本身的位置产生一次贡献，那么这类贡献总共有 $O(n)$ 个，按一般的做法处理即可
然后考虑剩下的贡献必然是这个点的两棵子树中分别取一个点
但是这样的点对个数过多了，显然不可取，我们考虑减掉无用点对
不难发现，对于三对 合法 点 $(u, v), (u, w), (v, w)$，若 $u<v<w$ ，那么显然 $(u, w)$ 是不可能计入贡献的。
因此能和一个点形成一个 计入贡献的合法点对 必然是它和它在其他子树内的前驱后继
考虑我们在更前面的点处产生贡献，那么就是它在其他子树内的前驱
那么就转化为了一个经典的问题，可以用 dsu on tree 解决
然后发现复杂度也一并解决了，仔细思考一下会发现这东西的复杂度分析和 DSU on tree 是类似的，访问到的点数是 $O(n\log n)$ 级别的，而每一个点产生的贡献是 $O(1)$，因此这样的点数就是 $O(n\log n)$ 的
因此总共是 $O(n\log n)$ 次单点修改和前驱后继操作，然后是 $O(q)$ 次区间修改
由于本题 $n, q$ 不同阶，直接上树状数组就行了
最终复杂度 $O(n\log^2 n+q\log n)$
标签：树状数组
整点亲民的 Ynoi
首先我们发现一旦修改就要一直修改
因为不难发现对于一个凸位置，无论怎么修改它都还是凸的
因此我们仔细分析，发现答案就是所有 “会凸” 的位置的和
那么我们现在就是要维护出这些位置，然后显然可以直接查询了
先说句废话：所有凸的位置一定是凸的
然后发现相邻两个凸的位置之间，似乎是隔一个加上一个这样子的
其实最后发现就是若干段奇偶位之和的和，然后每一次修改这个段的改变应该是 $O(1)$ 的
那么问题就在于求出这些段的具体答案
首先求这一部分显然可以树状数组直接搞
所以每一次就是 $O(1)$ 次单点修改，$O(1)$ 次区间查询（简单奇偶位分开即可），复杂度显然一只 $\log$
那么问题就只在于求出被改变的区间了
首先我们考虑能产生贡献的就是一个凸的位置然后往两边隔一个跳一个
发现会在凹的位置产生一些问题
并且考虑对于一个凹点，它必然是在左右两个凸点都能够到它的时候才被取到，因此一般判断时不考虑这个点
另外我们考虑比较的时候把下标当做第二维，值越小对应的二元组越大，这样就可以使得整个序列两两不同
另外实现时完全可以把 $0,n+1$ 当成两个极小点，然后权值为 $0$，这样一定不影响答案
然后其实差不多就做完了
但是还是感觉直接实现要特判很多东西，感觉很不方便于是就看了下题解，发现如果不卡常的话直接把原贡献删掉然后加上新贡献就行。。。
不愧是 DPair，思维瓶颈都这么清新脱俗
所以以后还是要少卡常（（
标签：数据结构优化图上问题
首先看到这种题，不难想到数据结构优化建图
但是发现建虚点会影响连通性，因此考虑不直接建边
考虑我们一般 tarjan 求割点是怎么做的，发现其实就是求出所有没访问过的后继结点然后进行一系列操作，然后对所有访问过的后继结点求一个 low 的最值
考虑第一部分与 $m$ 无关，因此要是能够快速求出所有没有被访问过的后继就行
发现这里可以采用主席树，而且不难发现把一个点置为无法访问后所有树内的这个点都变成无法访问
因此用类似线段树上二分的方法就可以 $\mathcal{O}(\log n)$ 的时间内找到一个后继结点
然后考虑求 low，注意到 low <= dfn 一定成立（毕竟初值就是 dfn 而且单调减小），因此直接求所有后继 dfn 的最小值即可，发现可以在同一棵主席树上维护
所以把主席树建出来后直接做即可
复杂度 $O(n\log n)$