老板给我们布置了一个寒假作业，回家自己出题提供题面+std+数据+题解。

自己瞎出的一道题，然后自己做了五个多小时（逃

部分分

对于1,2测试点，令 $f_i$ 表示当前已经到了第 $i$ 天，且一定刷了第 $i$ 天的题（不然没法转移），最高能提高多少水平。

$f_i=\operatorname{max}${$f_j-(i-j-1)^2$}。

对于第三个测试点，输出所有 $w_i$ 总和即可。

~~综上前15分有手就行~~

第11个点放了一个蜜汁性质，~~其实我也没怎么考虑这个性质有啥用~~。

第四个点，卡常（bushi

第5，6个点估计暴力做法的话估计只有lxl能卡过去了（

$solution$

这题的本意是卡掉 $O(nlogn)$ 的做法，现在正解不加fread看来卡不掉了（（（

所以本来想开6e6的数据直接搞成了2e6。。。

~~貌似我透露了正解复杂度~~

这题显然我们应该先展开原式。

$f_i=f_j-(i-j-1)^2$

$=f_j-(i-(j+1))^2$

$=f_j-i^2-(j+1)^2+2i(j+1)$

$=f_j-i^2-j^2-1-2j+2ij+2i$

原式可以变形为：

$f_j=\operatorname{max}${$f_j-j^2-2j+2ij$} $+2i-i^2-1$

我们发现一个问题：里面的 $\text{max}$ 的 $2ij$ 既与 $i$ 有关又与 $j$ 有关。这是非常烦人的一点。

这里可以先考虑把 $j$ 全部放到一个单调队列中。如果 $a\le b$，且对于 $f_{i+1}$ 来说，选择 $f_b$ 转移比 $f_a$ 更优，那么可以删除 $a$ 这个元素。可是这个问题还是没有得到解决：$i$ 每增加 $1$，$f_j$ 这个决策点相对于其它决策点的差距还是会变化，怎么办呢？

反正我到这里就放弃来，去想啥差分线段树分块各种歪解。最后走投无路才滚回这个单调队列的想法/kk。

~~明示正解~~

容易发现，对于两个数 $x$ 和 $y$，对于当前计算的 $i$ 满足 $x\le y$ 且选择 $f_x$ 比 $f_y$ 更好时，$y$ 比 $x$ “更有前途”（相对于后面的 $f_i$，它减少的速度更慢），但当前 $x$ 比 $y$ 暂时优一点，此时可以预测 $y$ 什么时候（当 $i$ 大于等于多少时）会变得比 $x$ 更优（当然，可能它到 $f$ 计算完毕后都不会更优）。令 $b_i=f_i-i\times i-2\times i$，则当 $i$ 大于等于 $\frac{b_x-b_y}{2y-2x}$ 时 $y$ 开始反超 $x$ 了，对于今后的 $f_i$ 的计算，选择 $y$ 比选择 $x$ 一定更优了。

但是我们不可能去用一个 vector 啥的去存这些信息，不然还是超时（其实这玩意儿我开始就想过，但是最后整了半天放弃了最后才滚回这个想法）。

接着考虑以下情况：

对于 $x,y,z$，$x\le y\le z$，若 $y$ 超过 $x$ 的时间早与 $y$ 被 $z$ 超过的时间，则 $y$ 一定是没有价值的，因为无论什么时候它都无法成为最优的决策。再想一想，单调队列的基本原理不正是保证每个元素都是一定有用的，一定能在某个时刻派上用场吗？上面的话，根据上面 $y$ 超过 $x$ 的时间的式子，可以转换为：

若 $\frac{b_x-b_y}{2y-2x}\le \frac{b_y-b_z}{2z-2y}$，即$\frac{b_x-b_y}{y-x}\le \frac{b_y-b_z}{z-y}$ 时，可以删除 $y$。

所以对于这个特殊的“单调队列”，设它表示为 $q_1,q_2…q_t$（在实现中，这里 $1$ 是head指针，$t$ 是tail指针），其中的元素表示下标，它维护的是 $\frac{b_{q_i}-b_{q_{i+1}}}{q_{i+1}-q_i}$ 的单调性，如果其中的 $q_i$ 递增排序，则 $\frac{b_{q_i}-b_{q_{i+1}}}{q_{i+1}-q_i}$ 是递减排序的。

那么，我们怎么判断当前队列里的的某些元素已经被其它的决策点反超了呢？

其实被反超就意味着对于当前计算的 $f_i$，$\frac{b_{q_i}-b_{q_{i+1}}}{q_{i+1}-q_i}\le i$，而 $\frac{b_{q_i}-b_{q_{i+1}}}{q_{i+1}-q_i}$ 又是从前往后递减排序的，所以只需要从队首删除元素即可。

~~越来越像标准单调队列了，爷青回~~

什么爷青回啊这题不都做完了吗（（（

~~我不会告诉你我推式子算错了两次~~

注意std带了fread，如有不适敬请谅解（

$Code:$

#include <cstdio>
#include <queue>
#define int long long
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 131072, stdin), p1 == p2) ? EOF : *p1 ++)

char buf[131072], *p1, *p2;
inline int read() {
	char ch;
	int x(0LL), f(1LL);
	while ((ch = gc) < 48) if (ch == '-') f = -1;
	do x = x * 10 + ch - 48; while ((ch = gc) >= 48);
	return x * f;
}

inline int max(const int x, const int y) {return x > y ? x : y;}
int f[2000005], b[2000005], w[2000005], q[4000005], head = 1, tail = 1;

signed main() {
	int n, ans(-1e15);
	n = read();
	for (int i(1); i <= n; ++ i) w[i] = read();
	f[1] = w[1], q[1] = 1, b[1] = f[1] - 3;
	for (int i(2); i <= n; ++ i) {
		while (tail > head && b[q[head]] - b[q[head + 1]] <= i * 2 * (q[head + 1] - q[head])) ++ head;
		f[i] = max(w[i] - (i - 1) * (i - 1),
		f[q[head]] - (i - q[head] - 1) * (i - q[head] - 1) + w[i]);
		b[i] = f[i] - i * i - 2 * i;
		while (tail > head && (b[q[tail]] - b[i]) * (q[tail] - q[tail - 1])
		<= (i - q[tail]) * (b[q[tail - 1]] - b[q[tail]])) -- tail;
		q[++ tail] = i;
	}
	for (int i(0); i <= n; ++ i) ans = max(ans, f[i] - (1LL * (n - i)) * (n - i));
	printf("%lld", ans);
	return 0;
}

zqs`s blog

U149793题解

部分分

$solution$

$Code:$