P9842 [ICPC2021 Nanjing R] Klee in Solitary Confinement

~~你说得对，但是 Klee 比根号可爱捏~~

题意简述

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

分析

直接做肯定是不好做的，考虑转换思路，考虑区间 \(+k\) 操作的贡献。

假设已知 \(a\) 为众数，那么区间内值为 \(a-k\) 的数就回产生 \(1\) 的贡献，而值恰好为 \(a\) 的数就会产生 \(-1\) 的贡献。于是如果给定了 \(a\)，就要找到最大的贡献区间。

枚举区间肯定不可行，考虑到最后的众数一定为 \(a_i\) 或者 \(a_i+k\) 的某个值，于是对于序列的任意位置 \(i\) 统计 \(a_i\) 和 \(a_i+k\) 的贡献，依次累加，并在过程中去最大值作为答案。如果在某个位置时，\(a_i\) 的贡献小于 \(0\) 就舍去并重新开始计算（因为再继续做答案一定不会更优）。

注意需要特判 \(k=0\) 的情况，此时直接输出原众数即可。

这道题的特殊处理技巧还有通过把所有数 \(+2\times10^6\) 把值域从 \([-2\times10^6,2\times10^6]\) 提升到 \([0,4\times10^6]\)，这样就可以直接开数组当桶来统计答案。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 4e6 + 5, posi = 2e6;
int n, k, a[maxn], ans = -1, c[maxn], t[maxn];

signed main() {
//Fast IO
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		c[a[i] + posi]++;
		ans = max(ans, c[a[i] + posi]);
	}
	if (k == 0) {
		cout << ans;
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		t[a[i] + posi]--;
		if (t[a[i] + posi] < 0) t[a[i] + posi] = 0;
		t[a[i] + posi + k]++;
		ans = max(ans, c[a[i] + posi + k] + t[a[i] + posi + k]);
	}
	cout << ans;
	return 0;
}