Daltao's blog!

题目1：给定一个序列a1,…,ana1,…,an，要求回答qq个请求，第ii个请求给定三个参数li,ri,kili,ri,ki，要求找出区间al,…,aral,…,ar中出现次数超过ri−li+1kiri−li+1ki的最小的数，如果不存在则输出−1−1。其中n,q≤105n,q≤105，1≤k≤51≤k≤5

这个问题有很多做法。

第一种就是用莫队。莫队内部维护一个统计表，统计每个数在区间中出现的次数。且由于每次每个数出现次数变化最多为11，因此对于每个分块，分配一个链表数组，第ii个元素记录该分块中所有出现次数为ii的元素组成的链表。很显然这样我们不管某个数出现次数是加11还是减11，都可以O(1)O(1)完成，且最重要的是我们可以实时统计每个分块中的最大值。在回答请求的时候，我们可以利用分块中的最大值先找满足条件的编号最小的分块，之后在分块中暴力查找。因此总的时间复杂度为O((n+q)n−−√)O((n+q)n)。

莫队的做法优点是与kk无关，缺点是常数比较大，且必须离线请求。

第二种做法就是发现，对于某个回答，我们可以不断从区间中选择kk个不同的数，之后删除。最后留下来的数不超过k−1k−1个，我们可以证明结果一定在这留下来的数中。这种区间消除的方式，我们可以用线段树实现，这样每次线段树的查询和修改的时间复杂度都是O(k2log2n)O(k2log2⁡n)。之后如果验证结果呢，这个我们可以通过持久化技术加差分或者直接上倍增完成，校验一个数的时间复杂度为O(log2n)O(log2⁡n)，总的时间复杂度为O((q+n)k2log2n)O((q+n)k2log2⁡n)。

第二种做法的优点是支持在线（我们可以为每个数都开一个稀疏线段树），缺点就是kk不能过大。

还有一种非常简单的做法就是直接上持久化线段树+差分的技术。线段树的每个结点记录区间中每个数出现的次数。之后对于每个请求，我们暴力扫描线段树，加上一旦发现区间中总数少于阈值就直接退出的剪枝。可以证明一次请求，线段树每一层最多有kk个顶点被访问（因为阈值决定了每一层最多有kk个条件满足条件）。总的时间复杂度为O((n+kq)log2n)O((n+kq)log2⁡n)。

第三种做法可以充分利用kk很小的特性。但是kk比较大的时候还是用莫队比较好。

一道题目。

问题2：给定一个序列a1,…,ana1,…,an，以及qq个请求，每个请求指定一个区间l,rl,r，要求找到序列al,…,aral,…,ar中的众数（出现次数最多的数），如果有多个，就输出其中最小的。这里n,q≤105n,q≤105，要求在线处理请求

一道题目。

先离散化数据。

这道题目的核心是发现，要计算A∪BA∪B的区间众数，其仅可能为AA的区间众数，或者是BB中的某个元素。

上面这个观察允许我们用分块解决这个问题。按照大小n−−√n进行分块。

之后考虑一次请求，可以知道答案要么出现在区间两端的块中，要么就是区间中间部分的众数。

我们可以维护两个数组cc和pp。其中c(i,j)c(i,j)表示前ii块中jj的出现次数。这样我们可以利用差分的技巧来快速计算某个数字在连续块中总的出现次数。而p(i,j)p(i,j)表示第ii块到第jj块中的众数。数组cc可以直接暴力计算每一块的信息最后统计前缀和，而pp可以暴力枚举两端块，之后通过p(i,j−1)p(i,j−1)快速转移。预处理的时间复杂度和空间复杂度均为O(n1.5)O(n1.5)。

每次请求我们也能以O(n−−√)O(n)求解，枚举每个可能的众数即可（总共只有O(n−−√)O(n)种可能）。

总的时间复杂度为((n+q)n−−√)((n+q)n)。

问题3：给定一个序列a1,…,ana1,…,an，找到一段最长的子数组（从头部和尾部删除若干个元素得到），满足子数组中众数非唯一，如果不存在这样的子数组，返回00。其中1≤n≤1051≤n≤105。

昨天比赛的一道题目。

称满足众数非唯一的数组称为好数组。假设11为整个数组的一个众数，我们可以直接证明任意最长的好数组一定包含11，否则我们可以扩大数组两端得到以11为众数的另外一个更长的好数组。

接下来，我们来考虑如何求这样一个好数组。我们可以暴力枚举另外一个众数xx。找到xx出现次数大于等于11出现次数的子数组，我们可以发现这样的数组一定可以扩展为好数组。当然这样做时间复杂度会变成O(n2)O(n2)，一种方式就是使用分块。我们只枚举出现次数超过n−−√n的元素。而对于出现次数不超过n−−√n的元素，我们知道这样的区间中11的出现次数也不会超过n−−√n。于是乎我们可以分别对11出现次数为1,2,…,n−−√1,2,…,n暴力遍历数组aa，每次遍历都使用双指针，整体的时间复杂度为O(nn−−√)O(nn)。

存在众数的连续子序列计数

一个连续子序列称为是好的，当且仅当其中有一个数出现超过半数以上，这个数称为众数。

现在给定一个长度为nn的序列a1,…,ana1,…,an，要求统计有多少连续子序列是好的。

提供一道题目。

一种简单的思路是使用分块。先考虑所有出现次数不超过n−−√n的数，它们能形成的连续子序列长度不会超过2n−−√2n。因此我们枚举所有长度不超过2n−−√2n的连续子序列，如果它里面存在众数，且总数全局出现次数不超过n−−√n。

而对于出现次数超过n−−√n的数xx，我们可以构建一个序列bb，其中如果ai=xai=x，则bi=1bi=1，否则bi=−1bi=−1。问题就变成了有多少子数组和是正数。这个问题咋看之下需要维护一个树状数组来解决，但是实际上由于前缀和只会+1和-1，因此可以通过维护一个普通计数数组就可以了，于是这个新问题的时间复杂度为O(n)O(n)。而xx最多取n−−√n个数，因此总的时间复杂度为O(nn−−√)O(nn)。

下面讲另外一种思路，可以将时间复杂度优化到O(n)O(n)。

具体就是我们不分块处理，对于每个不同的数xx，我们都构建bb序列，并处理。很显然这样做的时间复杂度为O(nD)O(nD)，DD为aa序列中的不同数数目。

假设xx在aa中出现kk次，我们可以尝试将时间复杂度优化到O(k)O(k)。具体思路是我们可以把bb中连续的-1合并为到一起。假设有一块连续的-1左边界为ll，右边界为rr，且以l−1l−1为右边界的最大子数组和为LL，以r+1r+1为左边界的最大子数组和为RR，如果L+R−(r−l+1)≤0L+R−(r−l+1)≤0，这意味着不可能有好数组包含这一整块-1。因此我们可以把这一段-1删除到只剩下R+LR+L个，这不会影响我们的结果。可以发现这样做，会导致从左向右扫描的时候每个1最多会激活一个-1，同理从右往左扫描的时候每个1最多会激活一个-1。因此这样处理完后最多有2k2k个−1−1，我们需要处理的bb序列长度仅为3k3k，用同样的算法，我们可以O(3k)O(3k)处理。

总的时间复杂度为O(n)O(n)。