Namomo Spring Camp 每日一题Day 1 子串的最大差

Problem Statement

给你一个长度为\(n\)的数组\(a_{1,\dots,n}\)求:\(\sum_{l=1}^n\sum_{r=l}^n\max\limits_{l\leq i\leq r}\{a_i\}-\min\limits_{l\leq i\leq j}\{a_i\}\).

Solution

我们考虑拆贡献分别计算: \(\sum_{l=1}^n\sum_{r=l}^n\max\limits_{l\leq i\leq r}\{a_i\}\)和\(\sum_{l=1}^n\sum_{r=l}^n\min\limits_{l\leq i\leq r}\{a_i\}\).

这样我们考虑\(a_i\)能够称为区间最大值和最小值的范围.

对于最大值: 有一个基本的思路就是, 从大到小加入一个数\(a_i\), 那么它能够成为最大值的区间就是前面第一个\(l\)满足\(a_l\leq a_i\and l<i\)和第一个\(r\)满足\(a_r\leq a_i\and r>i\)那么\(a_i\)能够称为最大值的区间个数为\((i-l)\times(r-i)\)个. 特别地我们认为\(a_j=a_i\)且\(j<i\)时, 认为\(a_j\)称为区间最大值的优先级比\(a_i\)大. 比如\([j,i]\)这个区间满足\(a_j=a_i\)我们认为\(a_j\)是区间最大值, 而不是\(a_i\).

对于最小值: 和最大值情况相似, 我们从小到大加入一个数即可.

这显然可以用一个平衡树或者\(set\)维护, 时间复杂度为\(O(n\log n)\).

---

如果\(O(n\log n)\)常数过大的话是无法通过所有测试数据的.

我们考虑优化上述算法.

对于一个数\(a_i\)成为最大值区间个数: 我们\(a_i\)的左边要找到第一个成为最大值优先级大于\(a_i\)的下标, 记为\(l\). 和\(a_i\)的右边找到第一个成为最大值优先级大于\(a_i\)的下标, 记为\(r\).

我们可以知道如果两个数\(a_j\geq a_i\and j>i\)那么\(a_j\)成为最大值的优先级一定大于\(a_i\).

这可以用一个单调栈维护即可, 跑四遍单调栈算法, 特别地要注意边界(取等条件). 最小值做法类似.

Code \(O(n\log n)\)set.

# define Fast_IO std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
# include "unordered_map"
# include "algorithm"
# include "iostream"
# include "cstdlib"
# include "cstring"
# include "cstdio"
# include "vector"
# include "bitset"
# include "queue"
# include "cmath"
# include "map"
# include "set"

using namespace std;

const int maxm=5e5+10;

int N;
long long Sum_Min,Sum_Max;
pair<int,int> A[maxm];
set<int> LH;

int main(){
	static int i,X,Left,Right;
	static long long Delt;
	scanf("%d",&N);
	for(i=1;i<=N;i++) scanf("%d",&X),A[i]={X,i};
	sort(A+1,A+1+N);
//	for(i=1;i<=N;i++) printf("%d ",A[i].first);
	LH.clear();LH.insert(0),LH.insert(N+1);
	for(i=1;i<=N;i++){
		auto Now=LH.lower_bound(A[i].second);
		Right=*Now,Left=*(--Now);
		Delt=1LL*(A[i].second-Left)*(Right-A[i].second);
		Sum_Min+=Delt*A[i].first;
		LH.insert(A[i].second);
	}
	LH.clear();LH.insert(0),LH.insert(N+1);
	for(i=N;i>=1;i--){
		auto Now=LH.lower_bound(A[i].second);
		Right=*Now,Left=*(--Now);
		Delt=1LL*(A[i].second-Left)*(Right-A[i].second);
		Sum_Max+=Delt*A[i].first;
		LH.insert(A[i].second);
	}printf("%lld",Sum_Max-Sum_Min);
	return 0;
}

Code \(O(n)\)单调栈

# define Fast_IO std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
# include "unordered_map"
# include "algorithm"
# include "iostream"
# include "cstdlib"
# include "cstring"
# include "cstdio"
# include "vector"
# include "bitset"
# include "queue"
# include "cmath"
# include "map"
# include "set"

using namespace std;

const int maxm=5e5+10;

int N,A[maxm];
int Stack[maxm],top;
int Max1[maxm],Max2[maxm];
int Min1[maxm],Min2[maxm];
long long Ans;

int main(){
	static int i;
	static long long Delt;
	scanf("%d",&N);
	for(i=1;i<=N;i++) scanf("%d",&A[i]);
	A[0]=1e8+10;
	Stack[top=1]=0;
	for(i=1;i<=N;i++){
		while(top && A[i]>=A[Stack[top]]) top--;
		Max1[i]=Stack[top];
		Stack[++top]=i;
	}
	A[N+1]=1e8+10;
	Stack[top=1]=N+1;
	for(i=N;i>=1;i--){
		while(top && A[i]>A[Stack[top]]) top--;
		Max2[i]=Stack[top];
		Stack[++top]=i;
	}
//	for(i=1;i<=N;i++) printf("%d %d\n",Max1[i],Max2[i]);
	A[0]=0;
	Stack[top=1]=0;
	for(i=1;i<=N;i++){
		while(top && A[i]<=A[Stack[top]]) top--;
		Min1[i]=Stack[top];
		Stack[++top]=i;
//		printf("%d Stack[%d]=%d\n",Min1[i],top,Stack[top]);
	}
	A[N+1]=0;
	Stack[top=1]=N+1;
	for(i=N;i>=1;i--){
		while(top && A[i]<A[Stack[top]]) top--;
		Min2[i]=Stack[top];
		Stack[++top]=i;
	}
//	for(i=1;i<=N;i++) printf("%d %d\n",Min1[i],Min2[i]);
	for(i=1;i<=N;i++){
		Delt=1LL*(i-Min1[i])*(Min2[i]-i);
		Ans-=Delt*A[i];
		Delt=1LL*(i-Max1[i])*(Max2[i]-i);
		Ans+=Delt*A[i];
//		printf("%d:%lld %lld\n",i,1LL*(i-Min1[i])*(Min2[i]-i),(i-Max1[i])*(Max2[i]-i));
	}printf("%lld",Ans);
	return 0;
}

Link

Link 1: CF817D Imbalanced Array.

Link 2: Daimayuan Online Judge 436.