[C++知识库]C. Klee in Solitary Confinement（2021ICPC-南京）（公式推导）

The 2021 ICPC Asia Nanjing Regional Contest

Problem

给出一个长度为n的序列a（$1\le n\le 1e6,?1e6\le a[i]\le 1e6$）。
允许对这个数组的一段区间[l, r] 全部加上 一个整数 k ($?1e6\le k\le 1e6$),也可以不对任何区间执行该操作。
问：执行该操作后（或不执行），数组a中众数的最大数量。

Solution

补充：

1. 结合代码看上面的题解
2. 由于数组a中存在负数，所以需要离散化一下。这里可以简单的对每个数 加上 2e6即可。（之所以加上2e6，是因为，$a[i]?k>=?2e6$）
3. 注意数组的空间大小

Code

const int N = 4e6 + 6;
int X = 2e6;
int a[N/4], b[N/4];
vector<int> v[N];
int main()
{
	IOS;
	int n, k; cin >> n >> k;

	int maxn = 0;
	int minn = 0;//所有离散化后的数据的最大值
	for (int i = 0; i < n; i++)
	{
		int x; cin >> x;
		x += X;
		minn = max(minn, x + k);
		v[x].push_back(x);
		v[x + k].push_back(x);
		maxn = max({ maxn, (int)sz(v[x]), (int)sz(v[x + k]) });
	}
	
	if (!k)
	{
		cout << maxn / 2 << endl;
		return 0;
	}

	int ans = 0;
	for (int i = 0; i <= minn; i++)
	{
		if (v[i].size() == 0) continue;
		int m = sz(v[i]);

		for (int j = 1; j <= m; j++)
			a[j] = a[j - 1] + (v[i][j - 1] == i);//前缀和

		int L = -1;//注意
		for (int j = 1; j <= m; j++)
		{
			L = max(L, a[j - 1] * 2 - j);//最大前缀
			ans = max(ans, L + j + 1 - a[j] + a[m] - a[j]);
		}
	}
	cout << ans << endl;

	return 0;
}