2019 计蒜之道 初赛 第五场 浪潮面试题之数组（单调栈）

题目链接

题目大意：

思路：用单调栈维护最优决策的集合。
我们倒着遍历数组，每次遍历到的相当于 $i$i, 每次新建一个决策 $\{a_i,l_i,r_i,x\}${ai​,li​,ri​,x}，意为：当前最优 $x$x位置的时候包含的右端点区间为 $l_i,r_i$li​,ri​，然后更新是在top的两个决策之间，设两个决策分别为 $new=\{a_1,l_1,r_1,x\},pre=\{a_2,l_2,r_2,y\}$new={a1​,l1​,r1​,x},pre={a2​,l2​,r2​,y}，那么new的决策右端点r的范围可以扩大到pre的决策的 $l_2,r_2$l2​,r2​之中，我们每次二分一个极大位置 $pos,pos\in [l_2,r_2]$pos,pos∈[l2​,r2​]使得 $a_1\ast (pos-x+1)\ge a_2\ast (pos-y+1)$a1​∗(pos−x+1)≥a2​∗(pos−y+1),那么我们把新的决策范围扩大到pos即可，每次更新决策把旧的贡献减掉即可。
我们来分析一下二分的单调性：
1.若 $a_1\ge a_2$a1​≥a2​，必然满足
2.若 $a_1\&lt;a_2$a1​<a2​，由于 $1-x\&gt;1-y$1−x>1−y，我们 $pos$pos从小到大增加必然是要使得 $1-x\&gt;1-y$1−x>1−y造成的影响抵消， $pos$pos必然是一个极大的值刚好抵消影响,那么 $\le pos$≤pos的位置必然没有抵消完影响。
综上，二分的单调性成立。
细节见代码：

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e5 + 11;
struct uzi
{
	int d, l, r, i;
} Q[N];
int R, n, a[N];
const LL mod = 1e9 + 7;
LL res, tmp;
LL get(int l, int r) {
	return ((l + r + 0ll) * (r - l + 1ll) / 2ll) % mod;
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = n; i >= 1; i--) {
		for (Q[++R] = {a[i], i, i, i}; R > 1;) {
			auto l = Q[R], r = Q[R - 1];
			if (1ll * l.d * (r.r - l.i + 1) >= 1ll * r.d * (r.r - r.i + 1)) {
				Q[--R] = {a[i], l.l, r.r, l.i};
				tmp += mod - 1ll * r.d * get(r.l - r.i + 1, r.r - r.i + 1) % mod;
				tmp %= mod;
			} else {
				int x = r.l, y = r.r, ans = -1;
				while (x <= y) {
					int mid = x + y >> 1;
					if (1ll * l.d * (mid - l.i + 1) >= 1ll * r.d * (mid - r.i + 1))ans = mid, x = mid + 1;
					else y = mid - 1;
				}
				if (ans == -1)break;
				Q[R] = {l.d, l.l, ans, l.i};
				Q[R - 1] = {r.d, ans + 1, r.r, r.i};
				tmp += mod - 1ll * r.d * get(r.l - r.i + 1, r.r - r.i + 1) % mod;
				tmp += 1ll * r.d * get(ans + 1 - r.i + 1, r.r - r.i + 1) % mod;
				tmp %= mod;
			}
		}
		tmp += 1ll * Q[R].d * get(Q[R].l - Q[R].i + 1, Q[R].r - Q[R].i + 1) % mod;
		tmp %= mod;
		res += tmp;
		res %= mod;
	}
	cout << res << endl;
	return 0;
}