NC20806 区区区间间间(单调栈)

题目

给出长度为n的序列a，其中第i个元素为ai，定义区间(l,r)的价值为

请计算出：

输入描述

第一行输入数据组数T
对于每组数据，第一行为一个整数n，表示序列长度
接下来一行有n个数，表示序列内的元素

思路：
就是求所有子区间(区间长度大于1的子区间)的最大值减去最小值的和是多少。
我们对原式子拆分一下可得:

其中max(l,r)表示区间l到r的最大值，min(l,r)表示区间l到r的最小值。
那么问题就转化为 求所有区间长度大于1的子区间的最大值之和/最小值之和。
暴力的方法就是两个for枚举起点和终点去计算，会TLE
考虑单调栈，单调栈维护什么？ 维护以a[i]为区间的最大值，往左右两边去更新拓展。
正着跑一次单调栈，倒着跑一次单调栈就能维护出来l和r数组。
其中l[i]表示以a[i]为最大值，左边最多延伸到l[i]，r[i]表示以a[i]为最大值，右边最多延伸到r[i]
然后怎么计算呢？
右两种情况。
① a[i]作为一个区间的端点，那么可以选择的区间另一个端点就是r[i]-l[i]。
② a[i]作为区间中的一点，也就是区间的端点都没选。那么就是在l[i]到i之间选一个作为左端点，r[i]-i之间选一个作为右端点，乘法原理可得区间的个数为 (r[i]-i) * (i-l[i])
这样就处理出来拆分出来的和式的第一部分了。
第二部分怎么求？
让a[i]=-a[i]，那么求最小值，就等于取反后的求最大值，在跑一下上面的过程就好了。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int n;
int a[N] , l[N] , r[N];

ll work(){
    for(int i = 1 ; i <= n ; i++) {
        int j = i;
        while(j > 1 && a[j - 1] <= a[i])
            j = l[j - 1];
        l[i] = j;
    }

    for(int i = n ; i ; i--){
        int j = i;
        while(j < n && a[j + 1] < a[i])
            j = r[j + 1];
        r[i] = j;
    }

    ll ans = 0;
    for(int i = 1 ; i <= n ; i++) {
        ans += (ll)a[i] * (r[i] - l[i]);
        ans += (ll)a[i] * (i - l[i]) * (r[i] - i);
    }
    return ans;
}

int main(){
     int t;
     scanf("%d" , &t);
     while(t--){
        scanf("%d" , &n);
        for(int i = 1 ; i <= n ; i++)
            scanf("%d" , &a[i]);

         ll ans = work();
         for(int i = 1 ; i <= n ; i++)
             a[i] *= -1;
         ans += work();

         printf("%lld\n" , ans);
    }
    return 0;
}