算法日记10:SC62求和（单调栈）（共享求解）

一、题目

二、题解：

1、首先，我们看到题目的第一个想法，就是把样例答案如何求解给列出来，图例如下

2、通过分析样例，可以很清晰的发现每一个数字都有其管辖的区间，因此我们可以想到能否找到一个数字它所管辖区间的左端点和右端点

3、以5来举例，可以发现它一共管辖了$3\ast 3$个区间，所以它对答案的贡献为$9\ast 5=45$

• 3.1：因此，我们可以简单算出样例答案
  

4、但是，会出现一种出现重复数字的情况

• 比如，在下面这个样例中：就会出现管辖区间分配的特殊情况
  
• 这时，我们就需要规定一个明确的规则，（也就是规定好给谁，这里以左闭右开为例），也就是说我们规定，如果一个区间有重复元素，那么我们就把这个区间给靠右的元素，但是这个用代码如何实现呢？
  

5、我们可以用单调栈的思想的解决，找到左边第一个<=a[i]的值（因为等于也归它管，但是<就不归它管了），//找到右边第一个<a[i]的值（因为<=都不归它管）

//找到左边第一个<=a[i]的值
    ll top=0;
    for(int i=1;i<=n;i++)
    {
        while(top&&a[stk[top]]>a[i]) //栈不为空/栈顶元素>a[i]
        {
            top--;  //栈顶元素出栈
        }
        if(top==0) l[i]=0; //表示左边没有<=的数
        else l[i]=stk[top];

        stk[++top]=i;   //入栈
    }

    //找到右边第一个<a[i]的值
    top=0;
    for(int i=n;i>=1;i--)
    {
        while(top&&a[stk[top]]>=a[i]) //栈不为空/栈顶元素>=a[i]
        {
            top--;  //栈顶元素出栈
        }
        if(top==0) r[i]=n+1; //表示右边边没有<=的数
        else r[i]=stk[top];

        stk[++top]=i;   //入栈
    }

6、区间求解原理（数学原理）

• 在最后一步，我们使用sum+=a[i]*(i-l[i])*(r[i]-i)来求解，其实这非常好证明，如下：
  
• 以2举例，我们可以清晰看到证明过程，
• 这个点的贡献=$a[i]\ast (i-l)\ast (r-i)$

a[i]-->这个点的值
l-->左边第一个>a[i]的下标值
r-->右边第一个>=a[i]的下标值

三、完整代码如下

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 7;
ll a[N];
ll stk[N];
ll l[N], r[N]; //模拟单调栈，存储下标

void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    //找到左边第一个<=a[i]的值
    ll top=0;
    for(int i=1;i<=n;i++)
    {
        while(top&&a[stk[top]]>a[i]) //栈不为空/栈顶元素>a[i]
        {
            top--;  //栈顶元素出栈
        }
        if(top==0) l[i]=0; //表示左边没有<=的数
        else l[i]=stk[top];

        stk[++top]=i;   //入栈
    }

    //找到右边第一个<a[i]的值
    top=0;
    for(int i=n;i>=1;i--)
    {
        while(top&&a[stk[top]]>=a[i]) //栈不为空/栈顶元素>=a[i]
        {
            top--;  //栈顶元素出栈
        }
        if(top==0) r[i]=n+1; //表示右边边没有<=的数
        else r[i]=stk[top];

        stk[++top]=i;   //入栈
    }
    
    ll sum=0;
    for(int i=1;i<=n;i++)   //遍历相乘
    {
        sum+=a[i]*(i-l[i])*(r[i]-i);
    }
    cout<<sum<<'\n';
}


int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1; //cin >> _;
    while (_--) solve();
    system("pause");

    return 0;
}