51 nod 1215 数组的宽度

**题，写线段树的时候懒得写query_min了直接cv的max然后cv错了，找了半天。
就只需要找到每个区间最大的值相加减去每个区间最小的相加。然后每一个值他的贡献数是(mid-l+1)*(n-i+1).
正解是单调栈（不会写，等会了在补。

#include<bits/stdc++.h>
#define fp(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
typedef double dl;
using namespace std;

const int N=1e5+7;
const ll M=1e9+7;
const int INF=0x3f3f3f3f;

int a[N];
int n;
ll sum1=0;
ll sum2=0;

struct node{
    int l,r;
    ll maxn,st1;
    ll minn,st2;
}tr[N<<2];

void pushup(int u)
{
    if(tr[u<<1].maxn>=tr[u<<1|1].maxn)
    {
        tr[u].maxn=tr[u<<1].maxn;
        tr[u].st1=tr[u<<1].st1;
    }
    else 
    {
        tr[u].maxn=tr[u<<1|1].maxn;
        tr[u].st1=tr[u<<1|1].st1;
    }
    if(tr[u<<1].minn<=tr[u<<1|1].minn)
    {
        tr[u].minn=tr[u<<1].minn;
        tr[u].st2=tr[u<<1].st2;
    }
    else 
    {
        tr[u].minn=tr[u<<1|1].minn;
        tr[u].st2=tr[u<<1|1].st2;
    }
}

void build(int u,int l,int r)
{
    tr[u]={l,r};
    if(l==r)
    {
        tr[u]={l,r};
        tr[u].maxn=a[l];
        tr[u].st1=l;
        tr[u].minn=a[l];
        tr[u].st2=l;
        return ;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u); 
 } 


node query_max(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        return tr[u];
    }
    else 
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(r<=mid) return query_max(u<<1,l,r);
        else if(l>mid) return query_max(u<<1|1,l,r);
        else 
        {
            node root,left,right;
            left=query_max(u<<1,l,r);
            right=query_max(u<<1|1,l,r);
            if(left.maxn>=right.maxn)    root=left;
            else root=right;
            return root;            
        }    
    }
}

node query_min(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        return tr[u];
    }
    else 
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(r<=mid) return query_min(u<<1,l,r);
        else if(l>mid) return query_min(u<<1|1,l,r);
        else 
        {
            node root,left,right;
            left=query_min(u<<1,l,r);
            right=query_min(u<<1|1,l,r);
            if(left.minn<=right.minn)    root=left;
            else root=right;
            return root;            
        }    
    }
}

void cal1(int l,int r)
{
    if(l>r) return ;
    ll mid,maxn=0;
    mid=query_max(1,l,r).st1;
    maxn=query_max(1,l,r).maxn;
    //printf("maxn:%lld mid:%lld\n",maxn,mid);
    sum1+=1ll*(mid-l+1)*(r-mid+1)*maxn;
    cal1(l,mid-1);
    cal1(mid+1,r);
}

void cal2(int l,int r)
{
    if(l>r) return ;
    ll mid,minn;
    mid=query_min(1,l,r).st2;
    minn=query_min(1,l,r).minn;
    //printf("minn:%lld mid:%lld\n",minn,mid);
    sum2+=1ll*(mid-l+1)*(r-mid+1)*minn;
    cal2(l,mid-1);
    cal2(mid+1,r);
}

void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    build(1,1,n);
    cal1(1,n);
    cal2(1,n);
    printf("%lld\n",sum1-sum2);


}

int main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0),cout.tie(0);
    //int T; scanf("%d",&T)
    //for(int i=1;i<=T;i++)
        solve();
}