若一个数在一段区间内作为最大值存在，那么答案应该加上这个数
若一个数在一段区间内作为最小值存在，那么答案应该减去这个数
所以我们利用单调栈，高效求出a[i]在哪个区间内作为最大/最小值存在，从而确定，加/减多少次a[i]，最终得到答案
#include#include #include #include #include #include #include #define MAXSIZE 100005#define LL long longusing namespace std;const LL INF=1e19;LL a[MAXSIZE];int s[MAXSIZE];int main(){ int n,top; LL ans = 0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); a[n+1] = 0; top = 0; for(int i=1;i<=n+1;i++) { if(top == 0) { s[++top] = i; } else { while(top>=1 && a[s[top]] > a[i]) { ans -= (i-s[top])*(s[top]-s[top-1])*a[s[top]]; top--; } s[++top] = i; } } top = 0; a[n+1] = INF; for(int i=1;i<=n+1;i++) { if(top == 0) { s[++top] = i; } else { while(top>=1 && a[s[top]] < a[i]) { ans += (i-s[top])*(s[top]-s[top-1])*a[s[top]]; top--; } s[++top] = i; } } printf("%lld\n",ans); return 0;}