thupc2024 H

· · 题解

标算

标算是 O(n\log^2 n)，考虑维护每一个数的所有出现位置，每次进行删除操作，把附近的 O(\log n) 个被影响的 bit 重新计算，维护出现位置（支持插入删除查询最小值和集合大小）使用 set，由于删除次数不超过 O(\frac{n}{\log n})，总复杂度 O(n\log^2 n)。

能不能再给力一点啊？

我们实际不需要维护每一个数的出现位置，可以只维护当前长度的所有二进制数的出现位置，每次长度变化的时候重构整个串，由于长度变化仅有 O(\log n) 次，每次只需要线性建 set 即可，删除的复杂度由于只维护了当前长度，变为 O(n\log n)。

你再想想？

以下为赛时做法。

设当前询问长度为 k。

可以把 set 直接换成 vector，只需要维护当前所有长度为 k 的子串的值，每次查询时直接遍历整个 vector，由于每次插入只会被枚举一次，此时查询并删除的部分复杂度降至 O(n)。

能不能再给力一点啊？

建出 01trie，问题转化为叶子上插入删除，按照 bfs 序查询某个子树的 mn,sz。

设阈值 B，设 T=\log n-k。

当 T>B 时，操作次数至多 2^{\log n-B}，使用任意的 \log 数据结构维护上述操作，复杂度 O(\frac{n\log^2n}{2^B})。

当 T\le B 时，使用上述的重构整串的方法，复杂度 O(nB)。

取 B=c\log\log n，总复杂度 O(n\log\log n)。

能不能再给力一点啊？

我并没有得到线性的做法，但若每次只需统计 i 的出现次数，并给定一个 i 的出现位置将其删除，可以做到与上述做法无关的 O(n)。

初始时，以层数为 \frac{\log n}{2} 的所有节点作为关键点，维护每个叶子属于的关键点，以及每个关键点所属的 k 层点，将贡献记录在叶子所属关键点以及关键点所属 k 层点上。每次 k 变化时重构第二类所属关系并重新维护子树大小，k 超过 \frac{\log n}{2} 时类似地重构关键点设置，而第一类所属关系可以位运算得出。

复杂度为 O(\sum n^{\frac{2^k-1}{2^k}}\times \frac{1}{2^k}\log n)=O(n)。

如果有整个题目线性的做法，教一下教一下教一下谢谢喵