@[Static_int](/user/731608) 操作三中内部的块直接无需管，而两端直接重新排序即可，不会让复杂度爆炸
如果需要的话，我可以给出证明
by Gumbo @ 2022-06-24 22:17:33
@[OI_Beater](/user/478861) ook，因为本人没用过分块（
by Static_int @ 2022-06-24 22:24:07
@[OI_Beater](/user/478861) 真的吗，操作三内部的块为什么不要管呢
by Yahbim @ 2022-06-24 22:26:19
@[Static_int](/user/731608) 我看您 36 道黑题，70 多道紫题，真的没有一道是分块么
by Yahbim @ 2022-06-24 22:31:17
@[Yahbim](/user/372708) 真的，区间操作没一道分块
by Static_int @ 2022-06-24 22:32:21
基本都是线段树搞得
by Static_int @ 2022-06-24 22:33:17
@[OI_Beater](/user/478861) 不对啊，你桶排不就直接 $O(n)$ 了吗？这复杂度炸了啊
by Static_int @ 2022-06-24 22:35:35
@[Yahbim](/user/372708) 请问您在吗？我可以在此给出证明
by Gumbo @ 2022-06-25 17:51:45
@[OI_Beater](/user/478861) 我觉得有问题的不是时间复杂度，而是正确性
by Yahbim @ 2022-06-25 17:57:25
@[Static_int](/user/731608) 首先回答您的疑惑：
由于这里只有26个字母，所以我们的桶最多只有26项
然后，我将把操作三两边的不完整块暴力完成先前的标记修改行为$O(\sqrt n)$,再遍历之，统计数据$O(\sqrt n)$.
在这之后，我遍历每一个中间的整块，复杂度为块数$(O(\sqrt n))$，再使用操作一中类似的方法，循环每一个字母，并统计其块内数量($O(26\times \log \sqrt n)=O(\log n)$，
总共复杂度$O(\sqrt n\log n)$
然后我就统计完了数目，先将最开始的不完整块处理完毕($O(\sqrt n+\log n)$),之后遍历内部块($O(\sqrt n)$)，用一个变量保存当前到了哪个字母，如果当前数目大于块长，直接打标记($ O(1) $),否则暴力修改，**由于只有26个字母，所以中断的块最多26个**，复杂度（$O(26\times\sqrt n)$)=$O(\sqrt n)$。
综上，复杂度=$O(\sqrt n\log n)$
by Gumbo @ 2022-06-25 18:01:26