本篇博客针对今年个人排位赛第四场的E题。在说明这道题之前，先来看一点没有什么关联的东西。 # 区间众数 顾名思义，就是在这个区间内出现次数最多的数。 当然使用莫队解决这类问题，大家都比较熟练，不过这里主要讲一下不使用莫队的方法以及带修改的问题。 在解决区间众数前，我们可以做如下约定，记 `mode(a)`为集合`a`的众数。 ## 引理 `mode(A \cup B) \in mode(A) \cup B` ## 说明 这一个引理看上去好像很唬人，实际上是一个废话。 如果一个数既不是`mode(a)`也不属于集合`B`，那么这个数只可能在`A`集合中出现，这样它的出现次数一定不会大于`mode(A)`。 ## 算法 虽然这个引理好像讲了一句废话，实质上也讲了一句废话，但是还是有一点用处的。 我们不妨将`n`个数都分成`T`块，每一块的大小是`O(n/T)`。 考虑每一次的询问`[l,r]`，我们不妨让`l`在第`a`块，`r`在第`b`块，那么我们就可以将这个询问分为三个部分。 1.`[l,r]`与第`a`块的交集部分，也就是`l`到第`a`快的最后一个。 2.`[l,r]`与第`b`块的交集部分，也就是第`b`快的第一个到`r`。 3.第`a+1`块到第`b-1`快。 根据我们刚才的引理，我们说明这样一件事，即`[l,r]`的众数要么是第3部分的众数，要么是第1部分或第2部分的数。 然后我们只需计算这些数的出现次数并进行比较即可。这一部分我们可以选择二分这些数出现的位置来解决。 那么我们我们只需要`O(nT \log n)`即可完成对应的预处理，然后在`O(\frac{n}{T} \log n)`的时间完成每一次询问。 ## 优化 然后你会发现这个复杂度完全无法接受，这甚至比莫队还慢，除了能够在线没有任何优点。 那么我们有没有什么办法能优化一下呢。 不难发现，这个问题解决的瓶颈在于询问一个数在某个区间的出现次数，如果这个东西能优化，我们就可以做到莫队的复杂度（虽然好像还是没什么用）。 我们延续之前的操作，继续分块，对每个块处理某个数出现的次数。 第一部分，处理某个数在前`i`块出现次数。我们只需要`O(\frac{n^2}{T})`的复杂度即可完成处理。 第二部分，处理某个数在某一块的前缀的出现次数。我们可以采用重新标号的方法，由于每一块最多`O(\frac{n}{T})`个，只需要重新标号就可以把多余的空间省去。 最后我们可以取`T=\sqrt n`来实现和莫队相同的复杂度（听上去这个方法更没用了）。 ## 带修改 延续之前的想法，我们只需要修改`O(T^2)`对块的结果即可。 每对块维护每个值出现次数，最大出现次数以及出现了`i`次的值有几个。这部分和不带修改的莫队是一致的。 此时我们就可以在`O(1)`时间内完成一对块的修改。 接下来考虑询问某个数在区间的出现次数，也只需要暴力修改一下即可。 最后我们取`T= n ^ {2/3}`，总的复杂度为`O((n+q)n^{2/3})`，和回滚莫队差不多，唯一的优势是在线。 # 区间绝对众数 区间绝对众数和区间众数大体相同，也可以沿用上面的方法。不过因为绝对众数是出现次数超过`n/2`的数，因此我们还可以用一个比较奇妙的算法去优化。 ## 摩尔投票 每次从数组中选择两个不同的元素，然后将其从数组中删除，最后能剩下来的数，有可能为区间绝对众数。 ## 证明 首先区间绝对众数出现次数超过`n/2`，因此如果有区间绝对众数，那么一定能剩下来。 ## 算法 不难发现这个东西具有结合性，因此你可以考虑维护区间剩下来的数是什么，以及剩下的次数，然后用线段树维护一下即可，由于这样剩下来的数不一定是绝对众数，因此可以用二分位置的方法判断这个数在这个区间的出现次数，判断一下是否大于一半即可。 因此整个代码的复杂度为`O(n \log n) - O(\log n)` 同样的，由于我们使用了线段树，因此单点更新会比较容易。 如果不需要更新，可以使用猫树之类的结构优化掉`\log n` 。 然后我们就可以在不使用莫队的情况下解决个人排位赛第四场的E题。 # 补充 区间逆序对，不管是否需要在线，复杂度都是`O(n \sqrt n)`，大致思想与上述区间众数的思想一致。