题解 | #盾与战锤#

首先选择的是子序列，考虑对原序列排序没有影响。

理由是选择子序列相当于可以任意选数，所以排序之后从大到小取可以双向规约。

另外考虑对于不同的 $kk$，首先对排序后的攻击序列做一遍前缀和，便于查询它们的区间和。

如果我们直接枚举不同的 $kk$，然后考虑每一个长度为 $kk$ 的区间：

实际上这个区间的直接贡献是：（假如护盾效果用 $mm$ 表示）

$sum[l\dots r]-msum[l\backslash dots\; r]-m$

另外这个区间的贡献不会是负数，原理和【最大子段和】相似，考虑证明复杂度：

$O\left({\sum }_{k=1}^n{\displaystyle \frac{n}{k}}\right)=O(n\ln n)O\backslash left(\backslash sum\backslash limits\_\{k=1\}^\{n\}\backslash dfrac\{n\}\{k\}\backslash right)=O(n\backslash ln\; n)$

复杂度可过，代码实现：（非完整代码）

#define int long long
signed main(){
	int n = init(), m = init();
	for (int i = 1; i <= n; ++i)
		a[i] = init();
	std::stable_sort(a + 1, a + 1 + n);
	std::reverse(a + 1, a + 1 + n);
	for (int i = 1; i <= 2 * n; ++i)
		s[i] = s[i - 1] + a[i];
	for (int k = 1; k <= n; ++k) {
		int ans = 0;
		for (int i = 1; i <= n; i += k) {
			int j = i + k - 1;
			if (s[j] - s[i - 1] - m > 0)
				ans += s[j] - s[i - 1] - m;
		}
		print(ans), putchar('\n');
	}
}