P2787-语文1（chin1）-理理思维
Gumbo
·
·
题解
本文为 \color{black}{\text{P2787-语文1（chin1）-理理思维}} 的题解。
前置芝士：
本篇题解思路：
拿到一个问题，首先我们看问题的类型。
显然，这道题是一道数列操作题。
接下来，我们看数据范围，并依此分析最劣时间复杂度。
首先，复杂度的 $\mathcal O(m)$ 是少不了的，然后我们根据数据范围，推出单次操作的极限复杂度约为 $\mathcal O(\sqrt n \log n)$，也就是说我们最终的复杂度要做到 $\mathcal O(m\sqrt n\log n)$ 以内（事实上，本篇题解就是这个复杂度，稍后证明）。
在这里，我们先考虑朴素的，不太可能过的暴力：
对于操作一，直接遍历一遍即可，将次数累加。
对于操作二，直接遍历，暴力拍平。
对于操作三，直接暴力 `sort`。
分析完了，代码咱也别打了，没意义，肯定过不了。
那么下面就来讲一个不是正解的做法，事先提醒一下，我的做法需要吸氧。
---
相信吊打我的大佬们看到时间复杂度的时候，就已经知道我的方法是啥了，但是这里，我还是要赘述一下。（轻点，别打脸
对于整个数列，我们建立块状数组维护，并额外维护一个局部有序的数组。
这里的代码：
```cpp
unsigned char ori[MAXN];
unsigned char sot[MAXN];
```
`ori` 数组字面意思为：`origin`，也就是原数列（不是 `orz`）。
`sot` 数组字面意思为：`sorted`，也就是局部有序数组。
然后我们看操作：
### 操作一：统计字符个数。
这里做法其实有两种，其中有一种能把复杂度优化到 $\mathcal O(m\sqrt n)$ 的做法，另一种则是我的 $\mathcal O(m\sqrt n \log n)$ 的做法。
这样思考：我们有两种方法，一是将每一块的每一个数都准备好，查询时直接累加。
另一种方法：每次询问时再处理，多一个 $log$。
这里我使用的是 $log$ 做法，因为如果维护一个数组的话，虽然能降低一个 $log$ 的复杂度，但是在维护时会有一个 $26$ 的大常数，而我们的 $log$ 显然是到不了 $26$ 的，因此有时高复杂度的做法反而比低复杂度的大常数做法在一定的数据范围更占优势。
我们使用分块的经典思想，将整块先放在一边，先统计散块的贡献。
显然，这里直接暴力即可，不是复杂度瓶颈。
对于整块，这里就要利用我们之前维护的 `sot` 数组了（养你不是用来过年的）
我们直接借用一下 `STL` 的二分算法，当然，如果你非要手写，我也不反对。
直接找到第一个大于这个字符的字符的位置和第一个大于等于这个字符的字符的位置。（自行断句）
将这两个位置相减，就是这个块内的这个字符的数量。
当然，使用二分的前提是在比较意义内，符合规定的都在右边，不符合的都在左边，所以我们应当使用单调不降的 `sot` 来完成这个操作，而不是没有单调性的 `ori`。
我们设第一个大于的位置为 $r$，第一个大于等于的位置为 $l$，显然，$r$ 是最后一个这个字符的下一个位置（如果存在），因此个数 $=(r-1)-l+1=r-l$。
如果不存在等于，那么大于等于与大于完全等价，相减结果为 `0`。
操作一结束。
---
### 操作二：区间拍平。
这个操作和区间加差不多，是分块的基础操作，就不细讲了，只需要维护每块的 `tag`，然后其它操作的时候注意一下就可以了。
散块还是暴力，然后随手 `sort` 维护一下 `sot` 数组（块内排序，复杂度 $\mathcal O(\sqrt n\log n^{0.5})=\mathcal O(\sqrt n\log n)$。
---
### 操作三：区间排序。
这个才是这道题的毒瘤之处，如果没有这个操作，那么随便一个数据结构估计都能做了。
现在来看这个操作如何实现：
首先，如果我们直接 `sort`，那就是绝对过不了。
那如果我们使用一个高效的排序算法呢？值域这么小，桶排安排上！
朴素桶排： $\mathcal O(n)$ ，带着约 $26$ 的常数，过不了。
无解了吗？并不是。
我们把桶排给拆掉：桶排的实现无非就是先找到每个字符的个数，再一个个赋值。
我们手动一步一步来做：
既然是要找到个数，我们可以直接套操作一。
赋值的话，我们可以这样做：
首先，处理左边的散块，这里直接暴力即可，复杂度 $\mathcal O(\sqrt n\log n)$，别忘了我们还要维护 `sot`。
然后，对于中间的整块，我们每次判断当前剩余的最小字符是否够排满这个块，如果够，就直接打上修改标记。
如果不够，那对不起，只能暴力。
最后是右边的散块，和左边的同理。
---
本题解正文结束，代码有点长，就挂剪贴板了。
[$\colorbox{yellow}{\color{red}{\texttt{CODE}}}$](https://www.luogu.com.cn/paste/4xxqgn3q)
---
#### 非正文部分一：时间复杂度证明。
对于数组的构建，直接将 `ori` 与 `sot` 同步赋值，赋完值之后对 `sot` 的每个块进行 `sort`，复杂度 $\mathcal O(n\log n)$。
对于操作一，散块的处理复杂度为 $\mathcal O(\sqrt n)$，整块的处理复杂度为 $\mathcal O(\log n)$，整块的数量是 $\sqrt n$ 级别的，所以这一步的复杂度为 $\mathcal O(\sqrt n\log n+\sqrt n)=\mathcal O(\sqrt n\log n)$。
对于操作二，散块的处理复杂度为 $\mathcal O(\sqrt n\log n)$，整块为 $\mathcal O(1)$，块数在 $\sqrt n$ 级别，总复杂度 $\mathcal O(\sqrt n+\sqrt n\log n)=\mathcal O(\sqrt n\log n)$。
对于操作三，统计的复杂度和操作一相同，赋值的复杂度 $=\mathcal O(\sqrt n\cdot \text{不完整的块数}+\sqrt n)$，因为这里只有在两个字符的交界处才有可能出现不完整的部分，因此 `不完整的块数` 最多为 $26$，为常数级，所以总复杂度为 $\mathcal O(\sqrt n+\sqrt n\log n)=\mathcal O(\sqrt n\log n)$。
操作的次数是 $\mathcal O(m)$ 级别的，所以总复杂度为 $\mathcal O(n\log n+m\sqrt n\log n)=\mathcal O((n+m\sqrt n)\log n)$，约为 $\mathcal O (m\sqrt n\log n)$，可以通过此题。
---
非正文部分二：申请添加标签：`块状链表、块状数组、分块`。
---
提交审核原因：改一下分类。