题目
给定长为n(n<=5e3)的数组a(1<=ai<=1e9),
对于每个子数组,其美丽值定义为操作任意次,使得子数组增序的最小秒数
每次操作,你可以选择两个下标[l,r],将区间[l,r]排增序,代价是r-l秒
求所有子数组的美丽值之和
思路来源
hxu10代码
题解
感觉和BZOJ1345 序列问题Sequence(思维/单调栈)_Code92007的博客-CSDN博客类似
单调栈还是非常巧妙,每次补的时候都有一点惊艳的感觉
枚举左端点,单增遍历右端点,单调栈维护最大值,实际是一个递增的栈,
元素(mx,cost)表示(当前前缀最大值,当前前缀最大值所在的这段区间排序所需要的代价)
每次用当前值a[j]将大于当前值的最大值弹栈,
这表明如果a[j]左侧有一个比a[j]更大的数v,至少是要把a[j]换到v左侧的,
假设原来换v这段区间代价为cost,则当前为cost+1,
相当于用若干次弹栈将若干个区间合并为一个区间
弹栈完之后,将当前前缀最大值mx,和mx所在的区间的cost放入栈内,第一维保证了复杂度
比如,7 10 8 6 12 100,前缀最大值是7 10 10 10 12 100,
但扫到6了之后,弹栈完再放入的实际是(10,4),因为6把10和7都弹走了,把区间合并在了一起
cur维护的是当前这段区间的代价,由合并若干段区间进行累加文章来源:https://www.toymoban.com/news/detail-464386.html
sum维护的是自栈底到栈顶元素代价和,每弹一个就减,每放入一个就加文章来源地址https://www.toymoban.com/news/detail-464386.html
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(a) (int)(a.size())
#define fi first
#define se second
typedef pair<int,int> P;
const int N=5e3+10;
int t,n,a[N];
P stk[N];
int main(){
cin>>t;
while(t--){
cin>>n;
rep(i,1,n)cin>>a[i];
ll ans=0;
rep(i,1,n){
int c=0,mx=a[i],sum=0;
rep(j,i,n){
int cur=0;
while(c && stk[c].fi>a[j]){
mx=max(mx,stk[c].fi);
cur+=stk[c].se+1;
sum-=stk[c--].se;
}
sum+=cur;
mx=max(mx,a[j]);
stk[++c]=P(mx,cur);
ans+=sum;
}
}
cout<<ans<<endl;
}
return 0;
}
到了这里,关于Codeforces Round 873 (Div. 1) B1.Range Sorting (Easy Version)(单调栈)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!