区区区间间间(单调栈)

区区区间间间

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; 
}

牛客算法竞赛入门课第二节习题题解文章被收录于专栏

入门课第二节习题题解