蓝桥杯备赛 Day16 单调数据结构

单调栈和单调队列能够动态的维护，还需用1-2两个数组在循环时从单调栈和单调队列中记录答案

单调栈

要点

1.时刻保持内部元素具有单调性质的栈(先进后出),核心是:入栈时逐个删除所有"更差的点",一般可分为单调递减栈、单调递增栈、单调不减栈、单调不增栈，例如要求某个点左侧第一个比它大的点的值(或位置),如下图所示:
![[单调栈.png]]
最后一个5入栈前要把前面那个5弹出，保证严格单调递减
2.单调栈用STL的stack实现，stack的操作:

C++ 中的 STL 也提供了一个容器 `std::stack`
- 元素访问- `st.top()` 返回栈顶
- 修改- `st.push()` 插入传入的参数到栈顶- `st.emplace()`- `st.pop()` 弹出栈顶
- 容量- `st.empty()` 返回是否为空- `st.size()` 返回元素数量

百亿富翁

学习:
(1)这题就是典型的单调栈的使用，就是对于每栋楼，左边第一个比它高的楼房是哪个，右边第一个比它高的楼房是哪个（若不存在则输出−1）,利用单调栈来维护下标，两个数据记录答案即可
(2)可以开两个栈，也可以开一个栈中间清空即可

while(!st1.empty()){st1.pop();
}

(3)注意删除不满足的栈元素用while循环
代码:

#include <bits/stdc++.h>using namespace std;
const int N=7e5+10;
int n,a[N],l[N],r[N];
stack<int> st1,st2;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++)	cin>>a[i];l[1]=-1;if(a[1]>a[2])	st1.emplace(1);for(int i=2;i<=n;i++){//不满足条件删除,注意用while while(!st1.empty() && a[i]>=a[st1.top()]){st1.pop();}//获取编号if(!st1.empty())	l[i]=st1.top();else l[i]=-1; //当前编号入栈st1.emplace(i); }//清空栈/*while(!st1.empty()){st1.pop();}*/ r[n]=-1;if(a[n]>a[n-1])	st2.emplace(n);for(int i=n-1;i>=1;i--){//不满足条件删除while(!st2.empty() && a[i]>=a[st2.top()]){st2.pop();}//获取编号if(!st2.empty())	r[i]=st2.top();else r[i]=-1; //当前编号入栈st2.emplace(i); }for(int i=1;i<=n;i++){cout<<l[i]<<" ";}cout<<"\n";for(int i=1;i<=n;i++){cout<<r[i]<<" ";}return 0;
}

最大区间

区间最值相关的问题
学习:
1.此题求求 L,R 使 (R−L+1)⋅min⁡(AL,AL+1,…,AR)尽可能大，其中 min 表示最小值。转化为对于每一个元素Ai,求他作为最小值的区间(l[i],r[i])(即贡献),转化为求第 i 个元素左边第一个比它小的元素的下标和右边第一个比它小的元素的下标，最后区间长度-2即可，上面转换后的问题就是典型的单调栈问题
核心:将问题转化为对每个元素的独立分析，而不是直接枚举所有可能的区间(O(n^2)->O(n))
2.l数组和r数组的默认值:

vector<int> l(n+1,0);//l[i]记录第i个元素左边第一个比他小的元素序号,默认是0(因为答案是要序号+1的，表示能到第一个元素) vector<int> r(n+1,n+1);//r[i]记录第i个元素右边第一个比他小的元素序号,默认是n+1(因为答案是要序号-1的，表示能到最后一个元素) 

3.保证栈是严格单调递增的，注意有=号
代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=3e5+10;
int n,a[N]; //l[i],l[i]记录第i个元素左边第一个比他小的元素序号，r[i]记录第i个元素右边第一个比他小的元素序号 
stack<int> st;
ll res;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++)	cin>>a[i];vector<int> l(n+1,0);//l[i]记录第i个元素左边第一个比他小的元素序号,默认是0(因为答案是要序号+1的，表示能到第一个元素) vector<int> r(n+1,n+1);//r[i]记录第i个元素右边第一个比他小的元素序号,默认是n+1(因为答案是要序号-1的，表示能到最后一个元素) //先算左边比自己小的元素序号 for(int i=1;i<=n;i++){//严格单调递增(有=号) while(!st.empty() && a[st.top()]>=a[i])	st.pop();if(!st.empty())	l[i]=st.top();st.emplace(i);}//清空栈while(!st.empty())	st.pop();//再算右边比自己小的元素序号 for(int i=n;i>=1;i--){//严格单调递增(有=号) while(!st.empty() && a[st.top()]>=a[i])	st.pop();if(!st.empty())	r[i]=st.top();st.emplace(i);} for(int i=1;i<=n;i++){//cout<<"i="<<i<<" l[i]="<<l[i]<<" r[i]="<<r[i]<<endl;//注意要-2 res=max(res,(ll)(r[i]-l[i]+1-2)*a[i]);}cout<<res;return 0;
}

四元组问题

学习:
(1)此题我根据条件：
四个不同的下标 a,b,c,d，使得 a < b < c < d ，并且 nums[d] < nums[c]< nums[a]< nums[b]
想到寻找每个元素左边和右边第一个比它小的元素的下标，此元素就是b，然后左边的就是a，右边的就是c，如果nums[c]>nums[a],那么就循环c=r[c],不断缩小nums[c],直到nums[c]<nums[a]，或者不存在，最后判断nums[d]=nums[r[c]]存不存在即可,用单调栈解决
代码:

#include <bits/stdc++.h>using namespace std;
const int N=5e5+10;
int a[N],n;
stack<int> st;
bool res;
int l[N],r[N];int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++)	cin>>a[i];//严格单调递增 for(int i=1;i<=n;i++){while(!st.empty() && a[st.top()]>=a[i])	st.pop();if(!st.empty())	l[i]=st.top();st.emplace(i);}while(!st.empty())	st.pop();for(int i=n;i>=1;i--){while(!st.empty() && a[st.top()]>=a[i])	st.pop();if(!st.empty())	r[i]=st.top();st.emplace(i);}//遍历寻找b元素for(int i=1;i<=n;i++){if(res)	break;int ta=l[i],c=r[i];if(ta==0 || c==0)	continue;//让a[c]<a[ta] while(a[ta]<=a[c]){c=r[c];if(c==0)	break;}if(c==0)	continue;//寻找dif(r[c])	res=true; } cout<<(res?"YES":"NO");return 0;
}

单调队列

要点

1.队内元素具有单调性质，一般将“下标”作为队列中的元素，而不是“元素值”
2.队头是“最优的元素”，后面是候选元素，每次入队时会将“没有价值的元素”直接删除
3.常用于处理固定长度的区间最值(常用于滑动窗口问题)
4.单调队列和优先队列的区别:
(1)单调队列一般用双端队列deque实现，需要在队头和队尾进行操作。而优先队列用STL的priority_queue实现(本质是堆)
(2)单调队列保持队列中元素的单调性，而优先队列不保证单调性，只保证队头元素是最大或最小。
(3)单调队列常用于滑动窗口问题，优先队列常用于需要动态获取最大或最小元素的场景。
5.双端队列操作:

C++ 中的 STL 也提供了一个容器 `std::deque`（双端队列）
- 元素访问- `dq.front()` 返回队头元素 - `dq.back()` 返回队尾元素- `dq.at(index)` 返回指定索引位置的元素（带边界检查）- `dq[index]` 返回指定索引位置的元素（无边界检查）
- 修改- `dq.push_front(value)` 在队头插入元素  - `dq.emplace_front(args...)` 在队头直接构造元素 - `dq.push_back(value)` 在队尾插入元素  - `dq.emplace_back(args...)` 在队尾直接构造元素  - `dq.pop_front()` 移除队头元素  - `dq.pop_back()` 移除队尾元素 - `dq.insert(iterator, value)` 在指定位置插入元素 - `dq.erase(iterator)` 移除指定位置的元素- `dq.clear()` 清空所有元素 
- 容量- `dq.empty()` 返回是否为空 - `dq.size()` 返回元素数量   - `dq.max_size()` 返回可容纳的最大元素数量

买蛋糕

学习:
(1)典型的用单独队列来求固定长度为k的区间的最值(最大值和最小值都可以),用双端队列deque实现，比如要求长度为k的最小值，让双端队列单掉递增，队首front是最小值序号，要判断队首元素是否在(i-k+1,i)中，不再则弹出。判断要插入元素和队尾元素的大小，如果小于队尾元素，则弹出队尾元素。最终把队首元素放入mi数组中
(2)此题涉及(a / b) % mod,且mod= 998244353998244353是质数，可以用费马小定理+快速幂求逆元，得$$(a/b)\%mod=a\ast b^{(mod-2)}\%mod$$
[[Day17 数学]]
(3)最好有取模的都用long long,可以使用以下技巧快速修改:

#define int long longsigned main(){ //不能写int}

代码:

#include <bits/stdc++.h>#define int long longusing namespace std;
const int N=1e5+10,M=998244353;
int n,k,x,a[N],sum,cnt;
deque<int> dq1,dq2;//dq1单调递增，队头是最小值序号，dq2单调递减，队头是最大值序号 
int mx[N],mi[N]; //到k为止位置的最小值和最大值 int binpow(int base,int power){int res=1;while(power){if(power & 1){res=(res*base)%M;}base=(base*base)%M;power>>=1; //有个= }return res;
}signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>k>>x;for(int i=1;i<=n;i++)	cin>>a[i];//求长度为k的区间的最小值for(int i=1;i<=n;i++){//队头序号不在(i-k+1,i)之间则弹出，维护长度为kwhile(!dq1.empty() && dq1.front()<i-k+1)	dq1.pop_front();//插入元素比队尾元素小弹出队尾元素while(!dq1.empty() && a[i]<a[dq1.back()])	dq1.pop_back();//插入元素序号到队尾dq1.emplace_back(i);//获取到i位置为止的最小值mi[i]=a[dq1.front()]; } //求长度为k的区间的最大值for(int i=1;i<=n;i++){//队头序号不在(i-k+1,i)之间则弹出，维护长度为kwhile(!dq2.empty() && dq2.front()<i-k+1)	dq2.pop_front();//插入元素比队尾元素大弹出队尾元素while(!dq2.empty() && a[i]>a[dq2.back()])	dq2.pop_back();//插入元素序号到队尾dq2.emplace_back(i);//获取到i位置为止的最大值mx[i]=a[dq2.front()]; }//获取结果for(int i=k;i<=n;i++){if((mx[i]-mi[i])<=x)	cnt++;} cout<<cnt*binpow(n-k+1,M-2)%M<<endl;return 0;
}

子矩阵

学习:
(1)此题就是一维求长度为k的区间的最值的二维拓展，求区间长a，宽b的最大值和最小值，用双端队列实现单调队列，内部元素就是位置(i,j)的有序对即可
代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1005,mod=998244353;
ll a[N][N],res;
deque<PII> dqmin,dqmax;//队首是最小值、最大值,对内元素为(i,j) 
int n,m,ta,b;
ll resmin[N][N],resmax[N][N];int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m>>ta>>b;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}//算最小值 for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//不在(i-ta+1,i)(j-b+1,j)内出队列while(!dqmin.empty() && (dqmin.front().first<(i-ta+1) || dqmin.front().second<(j-b+1)))	dqmin.pop_front();//插入元素小于队尾元素，弹出队尾元素while(!dqmin.empty() && a[i][j]<a[dqmin.back().first][dqmin.back().second])	dqmin.pop_back();//插入元素到队尾dqmin.emplace_back(i,j);  resmin[i][j]=a[dqmin.front().first][dqmin.front().second];	}}//算最大值 for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//不在(i-ta+1,i)(j-b+1,j)内出队列while(!dqmax.empty() && (dqmax.front().first<(i-ta+1) || dqmax.front().second<(j-b+1)))	dqmax.pop_front();//插入元素大于队尾元素，弹出队尾元素while(!dqmax.empty() && a[i][j]>a[dqmax.back().first][dqmax.back().second])	dqmax.pop_back();//插入元素到队尾dqmax.emplace_back(i,j);  resmax[i][j]=a[dqmax.front().first][dqmax.front().second];	}}//算结果for(int i=ta;i<=n;i++){for(int j=b;j<=m;j++){ll t=(resmin[i][j]*resmax[i][j])%mod;res=(res+t)%mod;}} cout<<res;return 0;
}

游戏

学习:
(1)典型的用单调队列求区间最值问题
(2)学会输出浮点数(保留2位小数)
cout<<fixed<<setprecision(2)<<res;
(3)最后结果利用数学公式总结最大值和最小值的和都出现了(n-k+1)次，不用O(n^n)遍历算，O(n)就能解决，且还能约掉一个(n-k+1),如果不约，不能直接除以(n-k+1)*(n-k+1)，会越界
代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,k,a[N];
deque<int> dqmin,dqmax;
int minn[N],maxn[N];
ll sum,cnt,summin,summax;
double res;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++)	cin>>a[i];for(int i=1;i<=n;i++){while(!dqmin.empty() && dqmin.front()<i-k+1)	dqmin.pop_front();while(!dqmin.empty() && a[dqmin.back()]>a[i])	dqmin.pop_back();dqmin.emplace_back(i);if(i>=k)	summin+=a[dqmin.front()];	}for(int i=1;i<=n;i++){while(!dqmax.empty() && dqmax.front()<i-k+1)	dqmax.pop_front();while(!dqmax.empty() && a[dqmax.back()]<a[i])	dqmax.pop_back();dqmax.emplace_back(i);if(i>=k)	summax+=a[dqmax.front()];}sum=(n-k+1)*(n-k+1);/*for(int i=k;i<=n;i++){for(int j=k;j<=n;j++){cnt+=(maxn[i]-minn[j]);}}*/cout<<fixed<<setprecision(2)<<(summax-summin)*1.0/(n-k+1);return 0;
}

优先队列

要点:

1.动态维护和快速访问优先级最高（或最低）元素(只能访问队首元素，不能像双端队列既能访问队首元素，也能访问队尾元素)的问题
2.优先队列操作:

C++ 中的 STL 提供了一个容器 `std::priority_queue`（优先队列），它是一种特殊的队列，元素按照优先级排序，默认情况下最大元素位于队首。
- 元素访问- `pq.top()` 返回队首元素（优先级最高的元素），注意这里没有 `front()` 方法，因为优先队列的逻辑是总是访问优先级最高的元素。
- 修改- `pq.push(value)` 在队列中插入元素，插入后队列会自动调整元素顺序以保证队首元素优先级最高。- `pq.emplace(args...)` 在队列中直接构造元素，同样插入后会自动调整顺序。- `pq.pop()` 移除队首元素（优先级最高的元素）。
- 容量- `pq.empty()` 返回队列是否为空。- `pq.size()` 返回队列中元素的数量。- `pq.max_size()` 返回队列可容纳的最大元素数量。

合并果子

学习：
不断找最小的两个元素，使用优先队列获得，加起来得到t，结果加上t，再把t放到优先队列中
代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=1e4+10;
int n,a;
ll res; 
priority_queue<ll,vector<ll>,greater<ll>> pq;//队首是最小值 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a;pq.emplace(a);}if(pq.size()==1){res=pq.top();}while(pq.size()>1){int t1=pq.top();//cout<<"t1="<<t1<<endl;pq.pop();int t2=pq.top();//cout<<"t2="<<t2<<endl;pq.pop();res+=(ll)t1+t2;//cout<<"res="<<res<<endl;pq.emplace(t1+t2);}cout<<res;return 0;
}

最大开支

思想值得学习
学习:
1.此题要用优先队列动态维护每个项目的边际成本（即每增加一个人时，总成本的变化），通过计算对第i个项目从x-1个人增加到x个人所需钱的差，然后放到优先队列中，答案累加边际成本即可(含义是增加一个人的成本增加的最大值(不用管哪个项目)),最多n个人
代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int M=1e5+10;
int n,m,k[M],b[M],cnt[M];
ll res;
priority_queue<ll> pq;//返回第i个项目增加1个人所增加的钱数(即从x-1增加到x人)
//x(kx+b)-(x-1)(k(x-1)+b)=k(2x-1)+b
ll getCost(int i,int x){//ll res=max((ll)x*(k[i]*x+b[i])-(ll)(x-1)*(k[i]*(x-1)+b[i]),(ll)0);ll res=max((ll)k[i]*(2*x-1)+b[i],(ll)0);return res;
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++){cin>>k[i]>>b[i];}//算对于第i个项目增加1个人所需增强的钱数放到优先队列中 for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){//如果第i个项目j个人相对于j-1个人是增加钱的，放到优先队列中if(getCost(i,j)){pq.emplace(getCost(i,j)); }else	break;}}//计算num次(最多n个人，即最多增加n次>0的钱，但也有可能pq大小小于n，0不在里面)int num=min((int)pq.size(),n);while(num--){res+=pq.top();pq.pop();} cout<<res;//下面这种比较好理解int num=n;while(!pq.empty() && num>0){res+=pq.top();pq.pop();num--;}return 0;
}