孩子傻了，不会算数

critnos · 2024-07-14 21:16:17 · 算法·理论

退化至幼儿园水平。

今天在水 u 群。和裙友@H_Kaguya 讨论研究之后发现，之前一直以为单点修改区间最大值只能 O(1) 修改，O(n/\text{polylog}) 查询。这可能是一个天大的误会。只要能对修改的数排序（譬如值域是 \text{poly}(n)），就很可能至少是可以 O(1)-O(n^{o(1)}) 的。

首先一个单点修改为极小值（撤销掉这个元素的贡献）可以 O(1)-O(n^{o(1)}) 的。就是直接多层分块，每块里面排序，用链表维护。

然后每 O(n^{1-o(1)}) 次操作分为一组。对于一组，我们需要做的是支持撤销其中某个元素的贡献。用上面的方法维护。每 n 次操作（此时有 n^{o(1)} 组）O(n) 重构。

每次修改的时候，找到这个位置上次修改的时间，把这个位置撤销了，然后进入零散块中。如果零散块满了就重构一块。否则递归用上面的算法维护零散块。直到零散块大小是 n^{o(1)} 就暴力维护。

注意对下标排序使用基数排序。

upd：o(1) 指 \epsilon，一个极小的正常数。