P1318

Aryper · 2021-08-02 18:42:58 · 个人记录

积水面积

靠谱的单调栈做法。

时间复杂度 O(n) 。

注意细节。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e4;

ll ans,top,n,flg;

ll st[N+5],a[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read();flg=0;
        while(top>0&&a[i]>=a[st[top]]) {
            ans+=(i-st[top]-1)*(a[st[top]]-a[st[top+1]]);
        //  printf("test:%lld\n",(i-st[top]-1)*(a[st[top]]-a[st[top+1]]));
            top--;

        }
        if(top>0) {
            ans+=(i-st[top]-1)*(a[i]-a[st[top+1]]);
        //  printf("test:%lld\n",(i-st[top]-1)*(a[i]-a[st[top+1]]));
        }
        st[++top]=i;
    //  printf("test:ans=%lld\n",ans);
    }

    write(ans);

    return 0;
}