题面

有 $n$ 个数，第 $i$ 个数是 $a_i$ ，Bob 可以从第 $1$ 个数开始，依次考虑这些数选不选。

如果 Bob 同时选择了 $i,j(i<j)$ 两数则应该有 $a_i\le a_j$ 。

如果 Bob 不选择 $i$ , 并且这是连续第 $k$ 场没有选择的数，他将丢失 $k$ 点分数。

Bob 最终获得的值是所有选择的数 $a_i$ 之和减去丢失的分数的和。求这个值最大值。

$n\leq10^5,|a_i|\leq10^9$ 。

题解

$\mathcal{O}(n^2)$ 做法显然，考虑优化。如果没有 $a_i\le a_j$ 的限制就是直接斜率优化。有限制就在外面套层 CDQ 分治：按 $a_i$ 排序后 CDQ 分治，左半区间按原下标排序插入凸壳，右半区间按原下标顺序查询，查询时不断将队首弹出即可。时间复杂度 $\mathcal{O}(n\log n)$ 。

代码

const int N = 1e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	ll n;
	pair <ll, ll> a[N], t[N];
	ll f[N], q[N], c[N];
	double slope (ll x, ll y) { return (1.0 * c[x] - c[y]) / (y - x); }

	bool cmp (pair <ll, ll> a, pair <ll, ll> b) {return a.second < b.second;}
	void CDQ (ll l, ll r) {
		if (l == r) return;
		ll mid = (l + r) >> 1;
		CDQ (l, mid);
		ll p = q[0] = 1;
		for (ll i = l; i <= r; ++i) t[i] = a[i];
		sort(a + l, a + mid + 1, cmp);
		sort(t + l, t + r + 1, cmp);
		for (ll i = l, j = l; i <= r; ++i) {
			ll w = t[i].second;
			if (j <= mid && w == a[j].second) {
				while (p + 1 < q[0] && slope(q[q[0] - 2], w) > slope(q[q[0] - 1], w)) --q[0];
				q[q[0]++] = w;
				++j;
			} else {
				while (p + 1 < q[0] && q[p] * w + c[q[p]] <= q[p + 1] * w + c[q[p + 1]]) ++p;
				if (p < q[0]) {
					f[w] = max(f[w], f[q[p]] + t[i].first - (w - q[p]) * (w - q[p] - 1) / 2);
					c[w] = f[w] - w * (w + 1) / 2;
				}
			}
		}
	   	CDQ (mid + 1, r);
	}
	int main () {
		for (int t = Read(); t--; ) {
			n = Read();
			for (ll i = 1; i <= n; i++) {
				a[i] = make_pair(Read(), i);
			   	f[i] = a[i].first - (i - 1) * i / 2;
		        c[i] = f[i] - i * (i + 1) / 2;
			}
			sort (a + 1, a + 1 + n);
			CDQ(1, n);
			ll ans = -n * (n + 1) / 2;
			for (ll i = 1; i <= n; ++i) ans = max(ans, f[i] - (n - i) * (n - i + 1) / 2);
			printf("%lld\n", ans);
		}
		return 0;
	}
}

int main () {
	freopen("contest.in", "r", stdin);
	freopen("contest.out", "w", stdout);
	Main::main();
	return 0;
}