自动搬运

查看原文

来自洛谷，原作者为

	monstersqwq 急急急急急急寄寄寄寄寄寄

搬运于2025-08-24 22:53:28，当前版本为作者最后更新于2023-12-18 10:30:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

标算

标算是 $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)$。

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