专栏文章

题解：P9461 「EZEC-14」众数 II

EEricWan
P9461题解参与者 5已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@mino00bj
此快照首次捕获于
2025/12/02 05:32
3 个月前
此快照最后确认于
2025/12/02 05:32
3 个月前
查看原文
很有趣的一个题，下面说一下我做题的流程和思路来源。与大部分题解不同，本题解复杂度与值域无关，固定 O(n)O(n) 且常数较小，一发就是当时的次优解。
定义 f(i,j)f(i,j) 为 [bi…j][b_{i\dots j}] 的最小众数，先打个四次方暴力打表。
CPP
for (int i = 0; i < b.size(); i++) {
	for (int j = 0; j < i; j++) {
		cout << "0\t";
	}
	memset(buc, 0, sizeof(buc));
	int ans = 0;
	for (int j = i; j < b.size(); j++) {
		if (++buc[b[j]] > buc[ans] || (buc[b[j]] == buc[ans] && b[j] < ans)) {
			ans = b[j];
		}
		ansans += ans;
		cout << ans << '\t';
	}
	ans %= mod;
	cout << endl;
}
观察发现 f(i,j)∈{1,bi}f(i,j)\in\{1,b_i\}，当且仅当 bj≥bib_j\ge b_i 且 [bi,bj][b_i,b_j] 中间夹着的一些的 aa 没有比 bib_i 小的。这个结论可以证明，分讨即可，不证了。于是我们打出来还是四次方的暴力验证上面结论的正确性。
CPP
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= a[i]; j++) {
		ansans += j * (a[i] - j + 1);
	}
	int minn = INF;
	for (int j = i + 1; j <= n; j++) {
		minn = min(minn, a[j]);
		for (int k = 1; k <= a[i]; k++) {
			for (int l = 1; l <= a[j]; l++) {
				if (minn < k || l < k) {
					ansans++;
				} else {
					ansans += k;
				}
			}
		}
	}
}
我们一步步对着新的看起来更有前途的四次方代码优化，发现最终的答案可以如下计算得到：
CPP
for (int i = 1; i <= n; i++) {
	ansans += inv2 * a[i] * (a[i] + 1) * (a[i] + 1);
	ansans -= inv6 * a[i] * (a[i] + 1) * (a[i] * 2 + 1);
	int minn = a[i];
	for (int j = i + 1; j <= n; j++) {
		minn = min(minn, a[j]);
		ansans += -inv3 * minn * minn * minn;
		ansans += inv2 * minn * minn;
		ansans += -inv6 * minn;
		ansans += inv2 * minn * minn * a[j];
		ansans += -inv2 * minn * a[j];
	}
	ansans += a[i] * (suma - s[i]);
}
单层循环内计算的东西并不占用太多时间，双层循环中计算的那些东西只有可以建立小根笛卡尔树解决。
为了统计双层循环中计算的所有东西，我们需要知道：
∑i=1n−1∑j=i+1nmin⁡k=ijak\sum_{i=1}^{n-1}\sum_{j=i+1}^n\min_{k=i}^ja_k
∑i=1n−1∑j=i+1n(min⁡k=ijak)2\sum_{i=1}^{n-1}\sum_{j=i+1}^n(\min_{k=i}^ja_k)^2
∑i=1n−1∑j=i+1n(min⁡k=ijak)3\sum_{i=1}^{n-1}\sum_{j=i+1}^n(\min_{k=i}^ja_k)^3
∑i=1n−1∑j=i+1naj×min⁡k=ijak\sum_{i=1}^{n-1}\sum_{j=i+1}^na_j\times\min_{k=i}^ja_k
∑i=1n−1∑j=i+1naj×(min⁡k=ijak)2\sum_{i=1}^{n-1}\sum_{j=i+1}^na_j\times(\min_{k=i}^ja_k)^2
我们建立出小根笛卡尔树之后，就可以知道每一个元素作为最小值时的 ii 的范围和 jj 的范围，于是就知道元素作为最小值时的区间数量，同时使用前缀和也可以快速计算后两个东西。
CPP
#define MAXN 1000005
int n, ls[MAXN], rs[MAXN], sta[MAXN], statop;
long long a[MAXN];
mint suma, ansans, s[MAXN];
mint ans1, ans2, ans3, ans4, ans5;
void solve(long long id, long long l, long long r) {
	ans1 += mint(a[id]) * ((id - l + 1) * (r - id + 1) - 1);
	ans2 += mint(a[id]) * a[id] * ((id - l + 1) * (r - id + 1) - 1);
	ans3 += mint(a[id]) * a[id] * a[id] * ((id - l + 1) * (r - id + 1) - 1);
	ans4 += mint(a[id]) * (s[r] - s[id - 1]) * (id - l + 1) - mint(a[id]) * a[id];
	ans5 += mint(a[id]) * a[id] * (s[r] - s[id - 1]) * (id - l + 1) - mint(a[id]) * a[id] * a[id];
	if (ls[id]) {
		solve(ls[id], l, id - 1);
	}
	if (rs[id]) {
		solve(rs[id], id + 1, r);
	}
}
signed main() {
	ewin >> n;
	for (int i = 1; i <= n; i++) {
		ewin >> a[i];
		suma += a[i];
		s[i] = s[i - 1] + a[i];
	}
	sta[0] = statop = 1;
	for (int i = 1; i <= n; i++) {
		ansans += mint(a[i]) * (a[i] + 1) * (a[i] + 1) * 499122177;
		ansans -= mint(a[i]) * (a[i] + 1) * (a[i] * 2 + 1) * 166374059;
		ansans += mint(a[i]) * (suma - s[i]);
		if (i > 1) {
			while (statop && a[sta[statop - 1]] > a[i]) {
				rs[sta[statop - 1]] = ls[i];
				ls[i] = sta[--statop];
			}
			if (statop) rs[sta[statop - 1]] = i;
			sta[statop++] = i;
		}
	}
	solve(sta[0], 1, n);
	ansans -= ans1 * 166374059;
	ansans += ans2 * 499122177;
	ansans -= ans3 * 332748118;
	ansans -= ans4 * 499122177;
	ansans += ans5 * 499122177;
	cout << ansans << endl;
	return 0;
}

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...