对于每一个 $j$ , 考虑它对哪个 $i$ 有贡献.
考虑分成两部分,对左边/右边的贡献(即使$a_j\le a_i+p-\sqrt{|i-j|}$ 最大的 $j$),以下以计算每个 $ j $ 对右边的贡献 (即只考虑 $j \le i$) 为例.
从左往右枚举 $i$ .
(`Line 72:` `for (int i = 1; i <= n; ++i)`)
考虑在队列 $Q$ 中维护所有可能产生贡献的 $j$ , 它类似于一个单调队列:
(
``` cpp
int Q[MAXN];
int Qll = 1, Qrr = 0;
void Qpush(int x) { Q[++Qrr] = x; }
void Qpop() { ++Qll; }
int Qsize() { return Qrr - Qll + 1; }
```
)
* 如果 $h_i$ 小于等于 $Q$ 中的最大值, $i$ 一定不对后面的产生贡献.
* 检查 $Q$. 计算每个元素 $j$ 对当前 $i$ 的贡献, 贡献最大的 $j'$ 前面的元素在以后一定不会更优 (即过期了) 删除这些元素.
这个做法就过了,感觉是个优化的 $O(n \sqrt n)$ , 但是还是求一个 hack 吧.
by mikcf @ 2023-07-11 21:49:53