[nowcoderACM_223C][区区区间间间]

题目链接

思路

考虑用单调栈,栈顶为最大元素。当得到一个新值得时候,将这个值宇栈顶比较。因为栈顶是前面的最大元素。所以只要当前元素比栈顶大,那么肯定比前面的都大。只要将这个元素乘上前面的个数就行了。

然后考虑对于像5,4这样的情况应该怎么办。因为4比5小,所以当前四的贡献就是将前面的每个值都加上一遍。

代码

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 100000 +100;
ll a[N],q[N];
ll n;
ll work() {
    int tail = 0;
    ll now = 0,ans = 0;
    for(int i = 1; i <= n;++i) {
        while(a[i] > a[q[tail]] && tail) now -= a[q[tail]] * (q[tail] - q[tail - 1]),tail--;
        q[++tail] = i;
        now += a[i] * (q[tail] - q[tail - 1]);
        ans += now;
    }
    return ans;
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
        ll ans = 0;
        ans += work();
        for(int i = 1;i <= n;++i) a[i] = -a[i];
        ans += work();
        cout<<ans<<endl;
    }
    return 0;
}

一言

修行要有耐性,要能甘于淡泊,乐于寂寞。

全部评论

相关推荐

05-20 13:59
门头沟学院 Java
米黑子米黑子:你这个成绩不争取下保研?
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 15:39
希望奇迹发生的布莱克...:真的是 现在卷实习就是没苦硬吃
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务