P9842 [ICPC2021 Nanjing R] Klee in Solitary Confinement 题解（SPJ!!!）

[ICPC2021 Nanjing R] Klee in Solitary Confinement

题面翻译

给定 $n,k$ 和一个长为 $n$ 的序列，你可以选择对区间 $[l,r]$ 的数整体加上 $k$，也可以不加。最大化众数出现次数并输出。

题目描述

Since the traveler comes, People in Monstadt suddenly raise great interest in computer programming and algorithms, including Klee, the Spark Knight of the Knights of Favonius.

Being sent to solitary confinement by Jean again, Klee decides to spend time learning the famous Mo’s algorithm, which can compute with a time complexity of $\mathcal{O}(n^{1.5})$ for some range query problem without modifications.

To check whether Klee has truly mastered the algorithm (or in fact making another bombs secretly), Jean gives her a problem of an integer sequence $a_1,a_2,?,a_n$ along with some queries $[l_i,r_i]$ requiring her to find the mode number in the contiguous subsequence $a_{l_i},a_{l_i+1},?,a_{r_i}$. The mode number is the most common number (that is to say, the number which appears the maximum number of times) in the subsequence.

With the help of Mo’s algorithm, Klee solves that problem without effort, but another problem comes into her mind. Given an integer sequence $a_1,a_2,?,a_n$ of length $n$ and an integer $k$, you can perform the following operation at most once: Choose two integers $l$ and $r$ such that $1\le l\le r\le n$ and add $k$ to every $a_i$ where $l\le i\le r$. Note that it is OK not to perform this operation. Compute the maximum occurrence of the mode number of the whole sequence if you choose to perform (or not perform) the operation optimally.

输入格式

There is only one test case in each test file.

The first line of the input contains two integers $n$ and $k$ ($1\le n\le 10^6$, $?10^6\le k\le 10^6$) indicating the length of the sequence and the additive number.

The second line of the input contains $n$ integers $a_1,a_2,?,a_n$ ($?10^6\le a_i\le 10^6$) indicating the original sequence.

输出格式

Output one line containing one integer indicating the maximum occurrence of the mode number of the whole sequence after performing (or not performing) the operation.

样例 #1

样例输入 #1

5 2
2 2 4 4 4

样例输出 #1

5

样例 #2

样例输入 #2

7 1
3 2 3 2 2 2 3

样例输出 #2

6

样例 #3

样例输入 #3

7 1
2 3 2 3 2 3 3

样例输出 #3

5

样例 #4

样例输入 #4

9 -100
-1 -2 1 2 -1 -2 1 -2 1

样例输出 #4

3

提示

For the first sample test case, choose $l=1$ and $r=2$ and we’ll result in the sequence { 4 , 4 , 4 , 4 , 4 } \{4, 4, 4, 4, 4\} {4,4,4,4,4}. The mode number is obviously $4$ which appears $5$ times.

For the second sample test case, choose $l=4$ and $r=6$ and we’ll result in the sequence { 3 , 2 , 3 , 3 , 3 , 3 , 3 } \{3, 2, 3, 3, 3, 3, 3\} {3,2,3,3,3,3,3}. The mode number is $3$ which appears $6$ times.

For the fourth sample test case, choose not to perform the operation. The mode number is $1$ and $?2$ which both appear $3$ times.

$以上来自洛谷$
看完题目知道我为什么说”原神启动“了吧。（什么，不知道？一看你就没看这篇题解。）

重点声明：我不玩原神。

解题思路

这一套 ICPC 的问题全是关于原神的诶，出题人什么了？

正片开始

我们枚举最后众数为 $x$，则每次只需要单独考虑 $x$ 和 $x+k$。我们事先可以将每个数按数值大小，将位置插入 vector，则可做到均摊 $O(n)$。如果使用 $map$ 或者别的容器实现，则有运行超时的风险。

现在问题转化成有一个长度为 $m$ 的序列，序列仅由 $X$ 和 $Y$ 组成，用 $X_{l,r}$ 和 $Y_{l,r}$? 表示区间 $[l,r]$ 里 $X$ 和 $Y$ 的个数，则我们需要选择一个区间 $[l,r]$，使得 $X_{1,l?1}+Y_{l,r}+X_{r+1,m}$ 最大。

简单转化一下，则对于每一个 $r$，我们需要最大化 $X_{1,l?1}+Y_{l,r}+X_{r+1,m}=X_{1,l?1}+(r?l+1)?X_{l,r}+X_{r+1,m}$?。整理得到 $(2\times X_{1,l?1}?l)+(r+1?X_{1,r}+X_{r+1,m})$，即最大化 $2\times X_{1,l?1}?l$，记录前缀最大值转移即可，时间复杂度 $O(m)$。综上，时间复杂度为 $O(n)$。

然后，去写代码，复制到提交代码出，点击提交，就会 $AC$ ?

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 1e6 + 5;
int n, k, a[Maxn];
int tong[Maxn * 4][2], maxx, len;
vector<int> res[Maxn * 4];
int ans;
inline void work() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += 2e6;
		res[a[i]].push_back(a[i]);
		res[a[i] + k].push_back(a[i]);
		len = max(len, a[i] + k);
		maxx = max({maxx, (int)res[a[i]].size(), (int)res[a[i] + k].size()});
	}
	if (!k) {
		cout << maxx / 2 << endl;
		return;
	}
	int tmp;
	for (int i = 0; i <= len; i++) {
		if (res[i].size() == 0) {
			continue;
		}
		for (int j = 0; j < res[i].size(); j++) {
			tong[j + 1][0] = tong[j][0] + (res[i][j] == i);
			tong[j + 1][1] = tong[j][1] + (res[i][j] != i);
		}
		tmp = tong[1][0] - tong[1][1];
		for (int j = 1; j <= res[i].size(); j++) {
			tmp = max(tmp, tong[j - 1][0] - tong[j - 1][1]);
			ans = max(ans, tong[res[i].size()][0] + tong[j][1] - tong[j][0] + tmp);
		}
	}
	cout << ans << endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}