CodeForces – 1446D2 – Frequency Problem

根号分治好题。

题意

给出一个序列 $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]);
    }
}

注意 $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);
    }
}

在上面的代码中,$\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;
}

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇