【CodeForces-1446D2】Frequency Problem (Hard Version)

根号分治好题。

题意#

给出一个序列 $a_1, a_2\cdots, a_n$ ，求最长的子段，使得其中有至少两个出现次数最多的元素。

输出子段的长度， $1\leq n\leq 2\times 10^5$ .

题解#

引理及证明#

众数：一个序列中出现次数最多的数，可以有多个。

首先有一个关于众数的结论：答案子段的众数集合，一定包含原序列的众数。

可以通过反证法来证明：

记 $x$ 是原序列的众数，假设存在子段 $a_l, a_{l+1}, \cdots, a_r$ 是题目所求的最长子段，且子段的众数不包含 $x$ .

根据众数的定义，在 $a_{[1, l-1]}$ 和 $a_{[r+1, n]}$ 中一定还包含 $x$ 。不妨设左侧包含 $x$ ，即 $\exists a_p=x, p\in[1, l-1]$ .

考虑将子段 $a_{[l, r]}$ 向两侧扩展，把 $a_p$ 包含进去，这样使子段长度变大，下面说明一定存在方案可以包含 $a_p$ .

把 $a_{[l, r]}$ 扩展为 $a_{[p,r]}$ 后，

若其众数的出现次数不变，则 $a_{[p,r]}$ 即为更优答案。
若其众数的出现次数增加，那么我们继续扩展，使更多的 $x$ 被包含进去。由于 $x$ 是整个序列中出现次数最多的数，所以把 $x$ 一个一个加进去，最后就变成了上面的情况，可以满足条件。

因此，我们总可以找到一个比 $a_{[l,r]}$ 更优的答案，假设不成立。

所以结论成立。

思路#

先找到序列 $a$ 的众数 $x$ ，若存在多个众数，则答案为 $n$ .

对答案中众数的出现次数进行根号分治，分别采用不同的方法处理。

设 $\operatorname{C}$ 为答案子段的众数的出现次数， $x,y$ 表示答案子段的众数， $\operatorname{cnt_i}$ 为值 $i$ 在序列 $a$ 中的出现次数。

下面进行分类讨论。

$\operatorname{C} > \sqrt{n}$ 的情况#

由于答案子段一定包含众数 $x$ ，且 $\operatorname{C}>\sqrt{n}$ ，所以 $y$ 也满足 $\operatorname{cnt}_y>\sqrt{n}$ .

显然，满足这个条件的 $y$ 最多有 $\sqrt{n}$ 个，考虑枚举 $y$ 。

只需在 $\mathcal{O}(n)$ 的复杂度内求出：以 $(x,y)$ 作为众数的最大子段长度。

此时问题只与 $x,y$ 这两个值有关，需要用到一个常见套路，让 $x$ 的权值为 $1$ ， $y$ 的权值为 $-1$ ，其余为 $0$ .

只需在新序列中找：数值和为 $0$ 的最长子段。

对新数列维护前缀和 $s_i$ ，子段 $[l,r]$ 的数值和为 $0$ 等价于： $s_r=s_{l-1}$ ，只需记录每个 $s_i$ 的最早出现位置即可。

// 1. 答案区间中众数的出现次数 > sqrt(n)，枚举所有可行的数值check
for(int i = 1; i <= n; i++) if(cnt[i] >= Sqrt && i != mxval) {
    memset(L, 0, sizeof(L)); L[0 + N] = 0;
    for(int j = 1; j <= n; j++) {
        s[j] = s[j - 1] + (a[j] == mxval ? 1 : (a[j] == i ? -1 : 0));
        if(!L[s[j] + N] && s[j]) L[s[j] + N] = j; //注意这里下标可能为负，所以要都加上N
        else ans = max(ans, j - L[s[j] + N]);
    }
}

cpp

注意 $s_i\in[-n, n]$ ，记录最早出现位置的数组，下标需要整体 $i\leftarrow i+n$ .

$\operatorname{C} \leq \sqrt{n}$ 的情况#

考虑枚举 $\operatorname{C}$ ，只需在 $\mathcal{O}(n)$ 的复杂度内求出：众数出现次数为 $\operatorname{C}$ 的最大子段。

这可以用双指针解决，细节有点多。

// 2. 答案区间中众数的出现次数 <= sqrt(n)，枚举所有可行的答案，双指针判断是否合法
for(int C = 1; C <= Sqrt; C++) {
    memset(cnt, 0, sizeof(cnt));
    for(int l = 1, r = 1, C_cnt = 0; r <= n; r++) {
        cnt[a[r]]++; if(cnt[a[r]] == C) C_cnt++;
        while(l <= r && cnt[a[r]] > C) {
            if(cnt[a[l]] == C) C_cnt--;
            cnt[a[l++]]--;
        }
        if(C_cnt >= 2) ans = max(ans, r - l + 1);
    }
}

cpp

在上面的代码中， $\operatorname{C_{cnt}}$ 代表出现次数为 $\operatorname{C}$ 的数的个数，动态维护桶。

代码#

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10, N = 2e5;
int n, a[MAXN], ans;
int L[MAXN << 1], s[MAXN]; //情况一，L[i]为前缀和i第一次出现的下标，s[i]为前缀和
int cnt[MAXN]; //情况2，对于目前的尺取区间，cnt是对a[]的桶
int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	int Sqrt = (int)(sqrt(n));
	for(int i = 1; i <= n; i++) cin >> a[i], cnt[a[i]]++;
	int mxcnt = 0, mxval = -1;
	for(int i = 1; i <= n; i++) {
		if(cnt[a[i]] > mxcnt) mxcnt = cnt[a[i]], mxval = a[i];
		else if(cnt[a[i]] == mxcnt && a[i] != mxval) mxval = n + 1;
	}
	if(mxval == n + 1) { cout << n << endl; return 0; } //若众数有俩，直接输出n
//	1. 答案区间中众数的出现次数 > sqrt(n)，枚举所有可行的数值check
	for(int i = 1; i <= n; i++) if(cnt[i] >= Sqrt && i != mxval) {
		memset(L, 0, sizeof(L)); L[0 + N] = 0;
		for(int j = 1; j <= n; j++) {
			s[j] = s[j - 1] + (a[j] == mxval ? 1 : (a[j] == i ? -1 : 0));
			if(!L[s[j] + N] && s[j]) L[s[j] + N] = j; //注意这里下标可能为负，所以要都加上N
			else ans = max(ans, j - L[s[j] + N]);
		}
	}
//	2. 答案区间中众数的出现次数 <= sqrt(n)，枚举所有可行的答案，双指针判断是否合法
	for(int C = 1; C <= Sqrt; C++) {
		memset(cnt, 0, sizeof(cnt));
		for(int l = 1, r = 1, C_cnt = 0; r <= n; r++) {
			cnt[a[r]]++; if(cnt[a[r]] == C) C_cnt++;
			while(l <= r && cnt[a[r]] > C) {
				if(cnt[a[l]] == C) C_cnt--;
				cnt[a[l++]]--;
			}
			if(C_cnt >= 2) ans = max(ans, r - l + 1);
		}
	}
	cout << ans << endl;
	return 0;
}

cpp

题意#

题解#

引理及证明#

思路#

C⁡>n\operatorname{C} > \sqrt{n}C>n​ 的情况#

C⁡≤n\operatorname{C} \leq \sqrt{n}C≤n​ 的情况#

代码#

$\operatorname{C} > \sqrt{n}$ 的情况#

$\operatorname{C} \leq \sqrt{n}$ 的情况#