[luogu] AT2060 [AGC005B] Minimum Sum 单调栈_乘法原理

前言

传送门 :

题意

给定 n , a [ ] n,a[] n,a[]求

∑ l = 1 N ∑ r = l N m i n ( a l , a l + 1 . . . a r ) \sum_{l=1}^N\sum_{r=l}^Nmin(a_l,a_{l+1}...a_r) ∑l=1N​∑r=lN​min(al​,al+1​...ar​)

思路

一开始想到线段树,但是还是避免不了第二层循环的优化

因此考虑使用单调栈+乘法原理解决这种类型的题

我们可以先预处理出来 a [ i ] a[i] a[i]有效的区间 [ L ， R ] [L，R] [L，R]

因此对于当前的 a [ i ] a[i] a[i]所能提供的贡献就是 a [ i ] ∗ ( i − L [ i ] ) ∗ ( R [ i ] − i ) a[i]*(i -L[i])*(R[i]-i) a[i]∗(i−L[i])∗(R[i]−i)

对于求 a [ i ] a[i] a[i]所能扩展的区间无非就是找左边第一个小于自己的,右边第一个大于自己的

为了去重,我们另一边为小于等于,其另一边为小于即可

这种问题使用单调栈即可解决

Mycode

// Problem: AT2060 [AGC005B] Minimum Sum
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT2060
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;
const int N = 2e5+10;
int a[N];
stack stk;
int l[N],r[N];
ll ans;

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

	a[0] = a[n+1] = -0x3f3f3f3f;
	stk.push(0);

	for(int i=1;i