区区区间间间(单调栈)
区区区间间间
https://ac.nowcoder.com/acm/problem/20806
题目描述
给出长度为n的序列a，其中第i个元素为aia_iai，定义区间(l,r)的价值为
vl,r=max(ai−aj∣l⩽i,j⩽r)v_{l,r} = max(a_i - a_j | l \leqslant i,j\leqslant r)vl,r=max(ai−aj∣l⩽i,j⩽r)
请你计算出∑l=1n∑r=l+1nvl,r\sum_{l = 1}^n \sum_{r = l + 1}^n v_{l,r}∑l=1n∑r=l+1nvl,r
输入描述:
第一行输入数据组数T 对于每组数据，第一行为一个整数n，表示序列长度 接下来一行有n个数，表示序列内的元素
输出描述:
对于每组数据，输出一个整数表示答案
示例1
输入
3 3 4 2 3 5 1 8 4 3 9 20 2 8 15 1 10 5 19 19 3 5 6 6 2 8 2 12 16 3 8 17
输出
5 57 2712
说明
对于一组测试数据的解释： 区间[1, 2]的贡献为：4 - 2 = 2 区间[1, 3]的贡献为：4 - 2 = 2 区间[2, 3]的贡献为：3 - 2 = 1 2 + 1 + 2 = 5.
备注:
T⩽20,n⩽105,0⩽ai⩽105T \leqslant 20,n\leqslant 10^5, 0 \leqslant a_i \leqslant 10^5T⩽20,n⩽105,0⩽ai⩽105不保证数据随机生成！
思路
用单调栈O(n)进行维护。
先化简，将连加内的减号打开，求所有的子区间的最大值之和，最小值之和。
两遍单调栈计算当前元素作为最大值的时候的区间左右端点
求最小值的时候就把当前元素乘上-1，这样继续用求最大值的函数，刚好有了负号。
最后ans根据不同情况求和就行了。
注意开long long ans会爆int，在计算的过程中可能也会爆int，可以强转ll。
代码
//区区区间间间(单调栈)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n;
int a[N] , l[N] , r[N];
ll work()
{
for(int i = 1 ; i <= n ; i++)
{
int j = i;
while(j > 1 && a[j - 1] <= a[i])
j = l[j - 1];
l[i] = j;
}
for(int i = n ; i ; i--)
{
int j = i;
while(j < n && a[j + 1] < a[i])
j = r[j + 1];
r[i] = j;
}
ll ans = 0;
for(int i = 1 ; i <= n ; i++)
{
ans += (ll)a[i] * (r[i] - l[i]);
ans += (ll)a[i] * (i - l[i]) * (r[i] - i);
}
return ans;
}
int main()
{
int t;
scanf("%d" , &t);
while(t--)
{
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i++)
scanf("%d" , &a[i]);
ll ans = work();
for(int i = 1 ; i <= n ; i++)
a[i] *= -1;
ans += work();
printf("%lld\n" , ans);
}
return 0;
} 牛客算法竞赛入门课第二节习题题解 文章被收录于专栏
入门课第二节习题题解
查看14道真题和解析