Neat trees（单调栈）

原题链接：

登录—专业IT笔试面试备考平台_牛客网

题意：

给定一个长度为1e6的序列hi(1e6),求所有连续区间的最大值减最小值的和。

解题思路：

首先暴力枚举每一个区间必定是超时的。那么考虑每个点对于答案的贡献值，可以这样想，对于点h[i]作为最大值在多少个区间出现，作为最小值在多少个区间出现？这个点对于答案的贡献就是h[i]作为最大值出现的次数 - h[i]作为最小值出现的次数，对于每个点，求一下贡献累加即可。

求每个点贡献的过程用单调栈来维护，拿求最大值的次数来举例。对于点i，找到左端第一个比h[i]大的数，记其位置为L，找到右端第一个比h[i]大的数，记其位置为R，则在（L,R）区间内包含点[i]的子区间个数就是 (i-L+1)(R-i+1)，可以画图理解一下。那么对于答案的贡献就是h[i](i-L+1)*(R-i+1)。

同理求出最小值的贡献，减去这个贡献，最终得到答案。

代码如下：

/*Keep on going Never give up*/#include using namespace std;#define MAX 0x7fffffff#define pi acos(-1.0)typedef long long ll;//int mon[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };const ll mod = 998244353;const int maxn = 1e6 + 100;ll a[maxn],l[maxn],r[maxn];stacks;int main() {ll n; while (cin >> n) {for (int i = 1; i > a[i];}for (int i = 1; i = a[i]) s.pop();if (s.empty())l[i] = 1; else l[i] = s.top() + 1;s.push(i);}while (!s.empty()) s.pop();for (int i = n; i >= 1; i--) {while (!s.empty() && a[s.top()] > a[i]) s.pop();if (s.empty())r[i] = n; else r[i] = s.top() - 1;s.push(i);}ll ans = 0;for (int i = 1; i <= n; i++)ans -= a[i] * (r[i] - i + 1) * (i - l[i] + 1);while (!s.empty()) s.pop();for (int i = 1; i <= n; i++) {while (!s.empty() && a[s.top()] = 1; i--) {while (!s.empty() && a[s.top()] < a[i]) s.pop();if (s.empty())r[i] = n; else r[i] = s.top() - 1;s.push(i);}for (int i = 1; i <= n; i++)ans += a[i] * (r[i] - i + 1) * (i - l[i] + 1);cout << ans << endl;while (!s.empty()) s.pop();}}