526互联

2023ACM暑假训练day 5-单调队列 单调栈

发布时间 2023-06-30 23:15:04作者: Qiansui

目录

DAY 5 单调队列/栈

训练地址：传送门

训练情况简介

早上：A、B、C、D题
下午：E题(未出，看了题解)、F题(暂时没有思路)
晚上：牛客小白月赛75+F、G题
6.30 记
今天仅做了单调栈的题，再练了一下相关题
后面的单调队列有两道都做过了，所以后面有时间记得补

A 题

题意：
给定一个数列，判断每个元素后第一个大于当前元素的下标，没有则为0
思路：
递减单调栈模板题

B 题

题意：
给定一个序列，代表每一只奶牛的高度，判断每一只奶牛在看到比自己高的奶牛前的奶牛数，最后输出总数
思路：
依旧是递减单调栈，与A题类似，但没有那么直接，得自己翻译一下题目

C 题

题意：
给你一个长度为n的序列，让你确定一个区间\([l,r]\)，满足\(1\leq l<r\leq n\)时，该区间内的最大值和次大值的异或和最大
思路：
这题有点妙哈，但也让我理解了单调栈的妙处！利用递减单调栈快速寻找区间的最大值和次大值
我们维护一个递减的单调栈，从前往后遍历。在出栈时，形成了一个序列，且当前元素为最大，栈顶元素为次大，ans统计结果的最大值；在进栈时，也形成了一个序列，当前为次大，栈顶为最大，更新异或最大值。最后输出答案即可。
总之，妙！这比\(O(n^3)\)寻找区间和区间的最大次大爽快多了

D 题

题意：
给你一个长为n的序列，让你确定是否对于所有区间\([l,r]\)，满足\(1\leq l<r\leq n\)时，该区间内的最大值大于等于该区间的和
思路：
依旧是利用递减单调栈存最大值，栈内存序列下标，每次进栈出栈都更新最大值与区间和的大小关系，即可得到答案
这里有个小问题，为什么仅考虑两侧即可？就是为什么进栈出栈的时候考虑就行，那不是有些序列（栈维护最大值递减，非递减则会出栈相应元素）没有考虑到吗？就是为什么仅考虑一个最大值的单左侧是否成立，单右侧是否成立即可？因为，除了当前元素，单左侧的元素满足和\(\leq0\)(因为当前元素值大于单左侧的和)，对于单右侧元素同理，故对于整个左右合并，除了当前元素的和仍小于0，故条件成立，满足题意
而且，从前面往后遍历数组，满足所有最大值的单左侧成立，之后在进栈的时候维护单右侧，使得单右侧依然成立，故整个栈都是成立的。
这题还可以再理解理解，写完代码后才发现里面的妙处！

E 题　未出，题解补

题意：
给你一个长度为n的数组，对于所有区间\([l,r]\)，满足\(1\leq l<r\leq n\)，求解\(\sum_{l=1}^{n-1}{\sum_{r=l+1}^{n}{次大值in [l,r] }}\)
思路：
主要就是对于每一个元素，我们都要考虑其对于最终式子的贡献，ans加上该点的贡献，即可得到最终答案
那么问题来了，怎么快捷地找一个区间的次小值，对于单调栈来说，找区间的最大值，次大值很容易，但是对于所有区间的最小值，次小值，就很吃力了应该，所以单单依靠一个单调栈估计很难求解
自己写的双向链表没法指向第二个大于自己的，，，或者说，想错了

洛谷的题解给了两种做法
做法一：单调栈+st表
很妙！
就是利用单调栈找到当前元素左右最近比自己最大的值，再利用两个st表快速找到左边和右边第二个最近的比当前元素大的数的位置，在统计求解即可
待学习st表和代码实现 实现后打勾 [ ]
做法二：双向链表
很妙！
利用双向链表实现上面思路的st表，直接在代码里给出注释

//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*
difficult...
思路来自洛谷，还在理解中，待摘记
这个从头开始的双向链表
前面的结果递推到后面
妙！
*/
const int maxm=1e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,a[maxm],L[maxm],R[maxm];

void solve(){
	cin>>n;
	ll t;
	for(int i=1;i<=n;++i){
		cin>>t;
		//对于每个数统计其位于数组中的位置
		a[t]=i;
		//其初始左右即标记为数组中位置的左右，后面会更新
		L[i]=i-1;
		R[i]=i+1;
	}
	ll ans=0;
	for(int i=1;i<=n;++i){//从小到大遍历数，同时更新L和R
		//l、r即为左右最近的比当前数大的下标
		int l=L[a[i]],r=R[a[i]];
		//左边存在区间时，必取左大1和当前，当前为区间次大值
		//再向两边扩展，两边扩展小于当前数的数，可能的区间数即为(左大1-左大2)*(右大-当前)
		if(l>=1) ans+=i*(l-L[l])*(r-a[i]);
		//右边存在区间时，必取右大1和当前，当前为区间次大值
		//再向两边扩展，两边扩展小于当前数的数，可能的区间数即为(右大2-右大1)*(当前-左大)
		if(r<=n) ans+=i*(R[r]-r)*(a[i]-l);
		//删去当前数的影响，因为它不可能成为接下来区间的次小数
		L[r]=l;R[l]=r;
	}
	cout<<ans<<'\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

相关资料：
妙哉！Second Sum！ - Acfboy 的博客 - 洛谷博客 (luogu.com.cn)

F 题 未出，题解补

题意：
给你一个长度为n的数组m，要求你再构造一个数组a，满足两个条件：
\(1. 对于所有的i\in[1,n]，有a_i\leq m_i\)
\(2. 满足1的情况下，对于所有的j<i<k\in[1,n]，a数组中不存在a_j>a_i<a_k\)
求在这两个条件下，数组和的最大值？
思路：
题目的意思是，对于你自己构造的数组，不能出现"V形"的样子，肯定是"倒V形"
那么最终可能的数组情况就只有三种情况：单调非递减、单调非递增、中间凸两边凹三种情况
所以我们可以利用单调栈来找前两种情况的最优值，同时记下前缀和后缀和，这是为了方便第三种情况的判断，具体可见代码

//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*
wa一发，思路有问题
题目好像还看错了！j < i < k是对于所有的下标的，而不是局部
那么最终的序列的可能情况：
单调非递增或非递减、中间凸两边凹三种情况
*/
const int maxm=5e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,a[maxm],l[maxm],r[maxm],ans[maxm];
ll suml[maxm],sumr[maxm];

void solve(){
	cin>>n;
	for(int i=1,j;i<=n;++i){
		cin>>a[i];
		//利用数组模拟单调栈
		j=i-1;
		while(j>0 && a[i]<a[j]){
			j=l[j];
		}
		l[i]=j;
		//更新前缀和
		suml[i]=suml[j]+1ll*(i-j)*a[i];//a[j+1~i]=a[i]
	}
	ll s=0,t;
	for(int i=n,j;i>0;--i){
		//利用数组模拟单调栈
		j=i+1;
		while(j<=n && a[i]<a[j]) j=r[j];
		r[i]=j;
		//更新后缀和
		sumr[i]=sumr[j]+1ll*(j-i)*a[i];//a[i~j-1]=a[i]
		//维护最大值，判断第三种情况的成立性
		if(suml[i]+sumr[i]-a[i]>s){
			s=suml[i]+sumr[i]-a[i];
			t=i;
		}
	}
	for(int i=t-1;i>0;--i){//从t向右维护数组a
		if(a[i]>a[i+1]) a[i]=a[i+1];
	}
	for(int i=t+1;i<=n;++i){//从t向左维护数组a
		if(a[i]>a[i-1]) a[i]=a[i-1];
	}
	for(int i=1;i<=n;++i){
		cout<<a[i]<<" \n"[i==n];
	}
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

相关资料：
题解传送门

G 题 看了cf数据，得wa启发

题意：
n个数依次排列，玩家初始位于第一个数上，玩家想抵达最后一个数上，但玩家的移动不是随意的，需要满足三个条件之一，才可以在第 i 和 j 个数上移动 (i < j)
三个条件为：
$1.i+1=j $
\(2. max(h_{i+1},...,h_{j-1})<min(h_i,h_j)\)
\(3. min(h_{i+1},...,h_{j-1})>max(h_i,h_j)\)
题目问你，玩家若最终抵达，最小的移动次数是多少？
思路：
注意不等号是严格不等号，又因为这个题在单调栈，所以判断移动时得注意相同数的影响
一个数组DP统计到达第 i 个数时所需要的最小移动次数
想要移动次数最小，就要充分利用2、3条件
对于第 i 个数，我们可以寻找其前面第一个大于/等于/小于的数，这三个数都可以作为移动的起点，之后利用这些起点更新第 i 个位置的移动最小值，从而递推实现整体最小
最终的答案即为\(dp[n]\)
wa5可能是因为移动的考虑不充分
wa13可能就是重复数的影响

补充内容

单调栈 Monotone Stack

【图解单调栈】两种方法，两张图秒懂
https://leetcode.cn/problems/next-greater-node-in-linked-list/solution/tu-jie-dan-diao-zhan-liang-chong-fang-fa-v9ab/
举例：返回每个元素两侧严格大于它的元素位置（不存在则为 -1 或 n）
如何理解：把数组想象成一列山峰，站在 a[i] 的山顶仰望两侧的山峰，是看不到高山背后的矮山的，只能看到一座座更高的山峰
这就启发我们引入一个底大顶小的单调栈，入栈时不断比较栈顶元素直到找到一个比当前元素大的
技巧：事先压入一个边界元素到栈底，这样保证循环时栈一定不会为空，从而简化逻辑
一些转换：
若区间 [l,r] 的最大值等于 a[r]，则 l 必须 > left[r]
若区间 [l,r] 的最大值等于 a[l]，则 r 必须 < right[l]
这一结论可以用于思考一些双变量的题目

https://oi-wiki.org/ds/monotonous-stack/
https://cp-algorithms.com/data_structures/stack_queue_modification.html

单调栈

矩形系列

字典序最小

贡献法

单调队列 Monotone Queue

两张图秒懂单调队列（Python/Java/C++/Go）
https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/solution/liang-zhang-tu-miao-dong-dan-diao-dui-li-9fvh/
需要不断维护队列的单调性，时刻保证队列元素从大到小或从小到大
前置知识：双指针
以固定窗口大小的区间最大值为例（此时维护的是一个从大到小的单调队列）：
每次向右移动一格左指针，在移动前，如果左指针指向的元素在队首左侧，说明左指针指向的元素小于队首，移动左指针不会改变区间最大值，直接移动左指针即可；
如果左指针指向的就是队首，那么移动左指针会使区间最大值变小（变为单调队列队首之后的那个元素），我们要弹出队首。
这样无论是何种情况，都保证了在移动左指针后，单调队列的队首始终为当前区间的最大值。
https://oi-wiki.org/ds/monotonous-queue/
https://oi-wiki.org/dp/opt/monotonous-queue-stack/
https://cp-algorithms.com/data_structures/stack_queue_modification.html
https://blog.csdn.net/weixin_43914593/article/details/105791217 算法竞赛专题解析（13）：DP优化(3)--单调队列优化
todo https://xyzl.blog.luogu.org/DQ-OP-DP