Ynoi 合集

注：无特殊说明的情况下，\(m\) 和 \(q\) 等都视为与 \(n\) 同阶。

[Ynoi2010] Fusion tree

感觉很具有启发性的题目。首先我们对于每一个点维护其儿子所组成的 01-trie。父亲的操作就单独处理即可。那么我们的目标其实很明确：就是执行一个对字典树内所有元素加 \(1\) 的操作。

而这个操作怎么做呢？我们考虑把一个二进制数反插入 01-trie，具体讲，就是从低位到高位插入。这样你手玩一下就可以发现单次操作可以做到 \(\mathcal O(\log V)\) 了。

至于为什么会想到倒插？也许是加法的法则使然。反正这个 trick 记住就行了。

updated on 2024.8.31：哎呀，好像找不到没写过题解的 Ynoi 了。只有炒冷饭了。

[Ynoi2019] 魔法少女网站

当初做这个题的时候就是用的序列分块。感觉其实挺好的。

我们考虑逐块处理。实际上我们就是令小于等于 \(x\) 的位置为 1，大于的位置为 0，然后对每一个极长 1 段算贡献。那么散块部分就是很简单的，单点修改直接暴力。主要看整块部分。

我们可以知道任何时候整块产生的影响本质上只有 \(\mathcal O(B)\) 种。那么把这些暴力处理出来过后，查询时我们就可以 lower_bound 块内的权值序列找到相应的那一种直接计算。这个的处理用链表就可以了。至此我们得到了一个 \(\mathcal O(n\sqrt n\log n)\) 的做法了。

发现复杂度瓶颈在于 lower_bound。我们可以根号平衡，对于整个值域的数维护块内小于等于它的数的个数。这个问题是可以做到 \(\mathcal O(\sqrt n)-\mathcal O(1)\) 的。至此，本问题就得到了 \(\mathcal O(n^{1.5})\) 的解法。

实际上这个做法挺平凡的，没有用到什么比较人类智慧的 trick，思路也较为自然。

[Ynoi2009] pmrllcsrms

远古题了，补一个题解。

考虑按 \(c\) 分块。单个块内的直接暴力，然后把块看成整体再维护另外一颗线段树。剩下的情况只有可能是两个块间的情况。去掉 corner cases，我们现在考虑如下情况：

第一个块是 \(1\) 到 \(c\)，第二个块是 \(c+1\) 到 \(2c\)。把两个块叠在一起，那么所选区间左端点必定在右端点右边。

也就是有两个数组 \(\text{pre}\) 和 \(\text{suf}\)，每一次操作区间修改某个数组的值，或者询问选出 \(1\le i<j\le c\) 使得 \(\text{pre}_i+\text{suf}_j\) 最大。这是比较易于线段树维护的。然后依然是用一颗大线段树把每两个块之间的贡献穿起来。

大致思路就是这样，但是细节很多，比如散块，长度不足 \(c\) 的块，以及被某个块包含的询问区间等等，而且很卡常。时间复杂度 \(\mathcal O(n\log n)\)。评价一下就是敢往这方面想就能会。