洛谷 P6503 分析（别看）

科技起源

2026-07-07 13:02:41

发布于：河北

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：求一个具体数值

1.2 题目背景、允许、禁止与限制

背景：有一个有 $n$ 个数的序列 $a$
允许：定义一个子序列的权值为子序列中最大值与最小值的差，求出所有连续子序列的权值之和
禁止：
限制：连续子序列

1.3 题目数据范围与猜测

$2 \le n \le 3\times10^5 \longrightarrow O(n)$

1.4 一句话概括题意

有一个序列，定义一个子序列的权值为子序列中最大值与最小值的差，求出所有连续子序列的权值之和

2 题目破题推导

注：以下六种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

首先我们要知道：要想使最终连续子序列权值之和更大，那就必须要使包含 $a_i$ 的区间越长（这样对于 $a_i$ 来说，包含 $a_i$ 的连续子序列的个数就越多）

那么，假设区间 $[i,j]$ 中的某个点 $k$ 保证 $a_k$ 是区间 $[i,j]$ 对应 $a$ 数组中元素中的最大值，并且这个区间是符合条件的最长区间，说明 $a_{i-1}$ 与 $a_{j + 1}$ 均 $>a_k$
接着，假设区间 $[i,j]$ 中的某个点 $k$ 保证 $a_k$ 是区间 $[i,j]$ 对应 $a$ 数组中元素中的最小值，并且这个区间是符合条件的最长区间，说明 $a_{i-1}$ 与 $a_{j + 1}$ 均 $<a_k$

那我们反过来思考
如果 $a_k$ 左边第一个比其小的元素位置是 $i$ ，右边第一个比其小的元素位置是 $j$ ，则区间 $[i+1,j-1]$ 就是以 $a_k$ 为最小值的最长区间
如果 $a_k$ 左边第一个比其大的元素位置是 $i$ ，右边第一个比其大的元素位置是 $j$ ，则区间 $[i+1,j-1]$ 就是以 $a_k$ 为最大值的最长区间

2.3 以终为始、以始为终

2.4 数学

2.5 分情况考虑

2.6 手动推导

2.7 边界测试

3 模型匹配

先提取关键词：左边第一个比其大右边第一个比其大右边第一个比其小左边第一个比其小
是 $\huge{单调栈}$

4 具体方案

4.1 单调栈维护

维护四个单调栈，分别代表左边第一个比其大、右边第一个比其大、右边第一个比其小、左边第一个比其小

4.2 计算答案

因为 $a + (b-c)=a+b-c$
因此维护一个ans变量，记录最终答案
我们知道如果 $a_k$ 被包含在区间 $[l,r]$ 内且是最大值，最终它对于这段区间的贡献就是 $a_k \times l \times r$
我们知道如果 $a_k$ 被包含在区间 $[l,r]$ 内且是最小值，最终它对于这段区间的贡献就是 $-(a_k \times l \times r)$

5 最终代码（禁止抄袭，仅用于参考）

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

const int N = 3e5 + 10;

int a[N];
int Lmax[N],Rmax[N],Lmin[N],Rmin[N];
stack<int>s;
int n;

signed main(){

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

    for(int i = 1;i <= n;i++){
        while(!s.empty() && a[s.top()] <= a[i]) s.pop();
        if(s.empty()){
		    Lmax[i]=0;
	    } else {
	    	Lmax[i] = s.top();
		}
        s.push(i);
    }

    while (!s.empty()) s.pop();
    for (int i = 1;i <= n;i++){
    	while(!s.empty() && a[s.top()] >= a[i]) s.pop();
    	if (s.empty()){
		    Lmin[i] = 0;
		} else {
			Lmin[i] = s.top();
		}
		s.push(i);
	}

    while (!s.empty()) s.pop();
    for (int i = n;i >= 1;i--){
    	while(!s.empty() && a[s.top()] < a[i]) s.pop();
    	if (s.empty()){
		    Rmax[i] = n + 1;
		} else {
			Rmax[i] = s.top();
		}
		s.push(i);
	}

    while(!s.empty()) s.pop();
    for (int i = n;i >= 1;i--){
    	while(!s.empty() && a[s.top()] > a[i]) s.pop();
    	if (s.empty()){
    		Rmin[i] = n + 1;
		} else {
			Rmin[i] = s.top();
		}
		s.push(i);
	}

    int ans = 0;
    for(int i = 1;i <= n;i++){
        ans += a[i] * (i - Lmax[i]) * (Rmax[i] - i);
        ans -= a[i] * (i - Lmin[i]) * (Rmin[i] - i);
    }
    cout << ans;

    return 0;
}