【单调栈 or 分治】51Nod1215[数组的宽度]题解

题目概述

给出一个序列 {An} ，求 ∑ni=1∑nj=imax{ai,ai+1,⋯,aj}−min{ai,ai+1,⋯,aj} 。

解题报告

水博客again，这道题显然是一道单调栈的题目（用单调栈处理出每个元素作为最大最小控制的区间累加答案就行了），不过这种题目也是经典的分治：

对于区间 [L,R] ，分成左边 [L,mid] 和 [mid+1,R] ，我们只需要考虑左边每个元素到右边的贡献：

记录 MAX(i,j)=max{ai,ai+1,⋯,aj} ，那么对于 i∈[L,mid] ， 右边的贡献为：

1. MAX(mid+1,j)≤MAX(i,mid) ，那么贡献为 MAX(i,mid) 。
2. MAX(mid+1,j)>MAX(i,mid) ，那么贡献为 MAX(mid+1,j) 。

累计一下前缀和就能快速计算出贡献了， min​ 同理。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=50000,MAXINT=((1<<30)-1)*2+1;
typedef long long LL;

int n,a[maxn+5];LL ans,Sx[maxn+5],Sn[maxn+5];

void Solve(int L,int R)
{
    if (L==R) return;int mid=L+(R-L>>1);Sx[mid]=Sn[mid]=0;
    for (int i=mid+1,now=-MAXINT;i<=R;i++) Sx[i]=Sx[i-1]+(now=max(now,a[i]));
    for (int i=mid+1,now=MAXINT;i<=R;i++) Sn[i]=Sn[i-1]+(now=min(now,a[i]));
    for (int i=mid,p=mid+1,now=-MAXINT;i>=L;i--)
    {
        now=max(now,a[i]);while (p<=R&&a[p]<=now) p++;
        ans+=Sx[R]-Sx[p-1]+(LL)(p-mid-1)*now;
    }
    for (int i=mid,p=mid+1,now=MAXINT;i>=L;i--)
    {
        now=min(now,a[i]);while (p<=R&&now<=a[p]) p++;
        ans-=Sn[R]-Sn[p-1]+(LL)(p-mid-1)*now;
    }
    Solve(L,mid);Solve(mid+1,R);
}
int main()
{
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    return Solve(1,n),printf("%lld\n",ans),0;
}