大号被禁言了。

请问一下我这么做为什么错了呢？

我用权值线段树 + 离散化 + 树状数组做的。

我们首先排除负数的 $a_i$。

我枚举最后一个看的电影，

然后我用权值线段树 + 离散化就可以求出第 $m$ 大的一场电影。

然后再用树状数组，求出后 $m$ 项的和 $sum$。

这样答案不就是 $sum - (d \times i)$。

但是 WA 了， 求调。

（赛场上写了15分钟，调了40分钟，交了5发，还是不知道哪里错，Rating -8，呜呜呜

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 200010;

int t[N];

void add(int u, int v) {
	for (; u < N; u += u & -u) t[u] += v;
}

int ask(int u) {
	int sum = 0;
	for (; u; u -= u & -u) sum += t[u];
	return sum;
}

int cnt[N];

void modify(int u, int l, int r, int x, int v) {
	// cout << u << endl;
	if (l == r) {
		cnt[u] += v;
		return;
	}

	int mid = l + r >> 1;
	if (x <= mid) modify(u << 1, l, mid, x, v);
	else modify(u << 1 | 1, mid + 1, r, x, v);

	cnt[u] = cnt[u << 1] + cnt[u << 1 | 1];
}

int query(int u, int l, int r, int rk) {
	if (l == r) return l;
	int mid = l + r >> 1;
	if (cnt[u << 1] >= rk) return query(u << 1, l, mid, rk);
	else return query(u << 1 | 1, mid + 1, r, rk - cnt[u << 1]);
}

int n, m, d;
int a[N], b[N];

void solve() {
	cin >> n >> m >> d;
	memset(cnt, 0, sizeof(int) * (n << 2));
	memset(t, 0, sizeof(t));
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	int tot = unique(b + 1, b + n + 1) - b - 1;
	for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int use = min(m, i);
		modify(1, 1, n, a[i], 1);
		// cout << "a[i]" << a[i] << endl;
		if (b[a[i]] <= 0) continue;
		add(a[i], b[a[i]]);
		int minn = query(1, 1, n, i - use + 1);
		// cout << "getkkk:"<< minn << "ues:" << use << ' ' << i - use + 1 << endl;
		ans = max(ans, ask(N - 1) - ask(minn - 1) - (d * i));
	}
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	while (T--) solve();
	
	return 0;
}