暑假集训第一周A,B题 （单调栈+乘法原理）题目解析（C++模板）

由上图得：

   本题要求的是当前数字序列a1，a2...,an的所有子区间的最小值之和。

而求所有子区间的最小值之和，也可以等价成以下说法：

求序列中上的的任意数在哪些区间上是最小值，用这些区间的个数num乘以当前数a[i]，为了方便说明，我们不妨把num叫做“当前数最小值的权值”。再对所有当前最小值的区间权值求和，即可得所有子区间上的最小值之和。

现在，我们不妨设最终答案为 result;

由上述推理，我们得到一个公式：（1）

（答案数量级评估：当前an的值最大可能为200000（2e5，若2e5个2e5则答案数量超过整数的范围，因此采用long long储存答案）

由（1）得，a[i]为已知的当前值，因此我们解决此题的关键转化为：求a[i]能成为最小值的所有子区间的个数。

怎么求呢？

我们知道，单调栈可以找到左起第一个比当前数字a[i]小的元素，和右起第一个比当前数字a[i]小的元素。

我们只需要找到这两个元素（不妨设这两个元素为a[j],a[k]），我们就找到了当前值可以作为最小值的最大子区间的左半边区间[j,i]和右半边区间[i,k].

接下来就是一个高中数学问题啦！(排列的乘法原理)

知道当前区间为[j,i]与[i,k]我们怎么求呢？在i~k上的子区间数的可能为{i} ,{i,i+1},{i,i+1,i+2}....到{i,i+1,i+2,.....k}共k-i个右端点的可能取值，而左边从开始也有i-j个左端点可能的取值。

第一步我们取右端点，有k-i个可能，第二步我们取左端点有i-j个可能，

那么两步一共有(k-i)*(i-j)种可能。

如果k=Rmin[i],j=Lmin[i],那么可得 

原公式转化为

解题代码如下：

#include
#include
#include
using namespace std;
typedef long long ll;//采用longlong来储存最终答案

const int N=2e5+10;

ll Lmin[N], Rmin[N], a[N];
//Lmin[i]储存当前值a[i]作为最小值可能取到的最左侧的下标,Rmin[i]为最右侧。
struct number {
    ll num, id;
}st[N];
//构造单调栈的结构体，st[N]为单调栈，每个数据包括两个数据元素：当前值和下标。

ll read(){//快速读数字的一个模板，写主函数读入的时候很方便。
    ll  x = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || '9' < ch)    f |= ch == '-', ch = getchar();
    while ('0' <= ch && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}


int main()
{
    
    ll n, i;
    //n为数据量，i为遍历控制指针 
    
    
    n = read();//读入n
    
    
    for (i = 1;i <= n;i++)
    {
        a[i] = read();//读入当前值

        //初始化
        Lmin[i] = 0;
        Rmin[i] = n + 1;
//如果不初始化的话，若第i个数是整体最小值，我写的方案中是栈非空时才执行
//赋值操作，这样一来这个最小值入栈前，栈是空的，那么它的左边界也就没有被赋值了 
    }
    
    ll s = 0;//单调栈栈顶指针 
    
    for (i = 1;i <= n;i++)//左遍历
    {
        while (s && st[s].num >= a[i]) s--;
        if (s) Lmin[i] = st[s].id;
        
        s++;
        st[s].num = a[i];
        st[s].id = i;
    }
    //每次构造单调栈之前都需要栈顶指针归0，防止奇怪的数值出现
    s = 0;
    for (i = n;i >= 1;i--)//右遍历与左遍历相似，也可以reverse一下，再一边左遍历。
    {
        while (s && st[s].num >= a[i]) s--;
        if (s) Rmin[i] = st[s].id;
        
        
        s++;
        st[s].num = a[i];
        st[s].id = i;
    }
    
    ll ans = 0;//求答案
    for (i = 1;i <= n;i++)
    {
        ans += a[i] * (i - Lmin[i]) * (Rmin[i] - i);//答案的公式
    }
    cout << ans << endl;//输出答案的格式
    return 0;
}

本质上是进行左遍历和右遍历，同时找到最大值和最小值本质上和第一种解法思路大体相同。

本题解题代码采用另外一种边界处理方式，同时用for循环的书写模板，相当于在数据两边加了很高很高的墙，让它被限制在里面，在寻找左边界和右边界的时候，不会发生数组越界。

#include
using namespace std;
typedef long long LL;

const int N=1e6+10;
LL a[N],b[N],mn[N],mx[N],mxl[N],mxr[N],mnl[N],mnr[N];
//a b 保存两次数据方便同时找最大值最小值 
LL read(){
    LL  x = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || '9' < ch)    f |= ch == '-', ch = getchar();
    while ('0' <= ch && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}

int main()
{
	int n,i;//
	LL ans=0,mns,mxs;//
	n=read();//
	for(i=1;i<=n;a[i]=read(),b[i]=a[i],i++);//
	a[0]=a[n+1]=-1E9,b[0]=b[n+1]=1E9;//防止第一个数向左寻找最小最大位置时越界 ，第n个数向右寻找最小最大位置时越界 
	for(mns=mxs=1,mn[1]=0,mx[1]=0,i=1;i<=n;i++)//往左找最大最小到的位置. 
	{
		for(;a[i]<=a[mn[mns]];mns--);
		mnl[i]=mn[mns],mn[++mns]=i;
		
		
		for(;b[i]>=b[mx[mxs]];mxs--);
		mxl[i]=mx[mxs],mx[++mxs]=i;
	}
	for(mns=mxs=1,mn[1]=mx[1]=n+1,i=n;i>0;i--)//往右找最大最小到的位置. 
	{
		for(;a[i]b[mx[mxs]];mxs--); 
		mxr[i]=mx[mxs],mx[++mxs]=i;
	}
	for(i=1;i<=n;i++)
		ans += a[i] * ( i -  mxl[i] ) * ( mxr[i] - i) 
		- a[i] * ( i - mnl[i]) * (mnr[i]-i);
	printf("%lld",ans);
	return 0;
}