好吧今天没有最小生成树的prim

一，单调栈

维护一个栈，使栈内所有元素严格保持单调递增或单调递减

实现过程

• 初始化空栈：栈中推荐存下标，而非数值，方便计算距离、边界
• 循环遍历数组每一个下标 i： while 栈不为空 且 当前元素破坏栈单调性： 弹出栈顶元素 top 此时 栈顶的目标边界就是 i，记录答案，将当前下标 i 压入栈

模板例题：找每个数字左侧第一个更小的数字

按照实现过程得到代码如下

#include<bits/stdc++.h> using namespace std; const int N=1e5+5; stack<int> st; int a[N]; int main(){ int n; 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()) cout<<"-1 "; else cout<<a[st.top()]<<" "; st.push(i); } }

真正的例题，区间最小值问题

给出正整数n和一个长度为n的数列，要求找出一个子区间，使这个子区间的数字之和乘上子区间中的最小值最大。

我们的思路如下，枚举区间左右端点搞贪心肯定不行

1≤n≤10^5​​,0≤a[i]≤10^​6​​

那我们的思路转移到最小值上，枚举每一个点作为一个区间的最小值，再反推求这个区间的左端点和右端点

那区间端点怎么求呢，一个数要想成为这个区间的最小值，显然这个区间里不能再有比它小的数，在它左边找第一个比它小的，那这个第一个比它小的右边自然都比它大了，在它右边找第一个比它小的，那这个第一个比它小的左边自然都比它大了，这样就得到了一个区间，而找第一个比它小的数的过程我们考虑单调栈，区间和直接采用前缀和

代码如下：long long 警告！+1-1警告

#include<bits/stdc++.h> using namespace std; const int N=1e5+5; stack<int> st; int a[N],L[N],R[N],sum[N]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=sum[i-1]+a[i]; } for(int i=1;i<=n;i++){ while(!st.empty()&&a[st.top()]>=a[i]){//留大的就是找左边第一个比自己小的 st.pop(); } if(st.empty()) L[i]=0; else L[i]=st.top(); st.push(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]=n+1; else R[i]=st.top(); st.push(i); } int ans=-1,l,r; for(int i=1;i<=n;i++){ if(ans<(sum[R[i]-1]-sum[L[i]])*a[i]){ ans=(sum[R[i]-1]-sum[L[i]])*a[i]; l=L[i]+1; r=R[i]-1; } } cout<<ans<<"\n"<<l<<" "<<r; }

本来想再放一个题但是都差不多其实就这样吧

二，单调队列

队列内元素保持单调递增 / 单调递减的双端队列叫做单调队列

求解问题：定长滑动窗口最大值、最小值

在这其中，想要的元素在队头，所以想要最小值从队头到队尾单调递增，想要最小值从队头到队尾单调递减，删除队头的情况：队头太远不在所求范围内。删除队头，无论如何要把a[i]插入队尾

实现过程：

• 队尾维护单调性新元素 a[i] 入队前：不断把队尾不如 a[i] 优的元素弹出。

• 以单调递减（求窗口最大值）为例： 若 a[i]≥a[q.back()]，队尾元素可以永久删除。

• 逻辑：只要 i 还在窗口里，队尾这个数永远不可能成为任何窗口的最大值，没有保留价值。

• 队头剔除过期元素窗口不断右移，如果队头下标 q.front()≤i−k，说明已经跑出窗口左边界，弹出队头。

• 维护单调的过程：
  若要添加的元素小于队尾元素，则不断末尾出队，直至队尾元素小于要添加的元素。
  维护长度的过程：
  若队列长度超过规定长度，则队头出队。

模板：滑动窗口最大值

for(int i=1;i<=n;i++){ while(!q.empty() && a[i] >= a[q.back()]){ q.pop_back(); } q.push_back(i); //注意存储下标 while(q.front() <= i - k){ q.pop_front(); } if(i >= k){ cout<<a[q.front()]<<" "; } }

回顾一下二维前缀和的二次扫描法

二维前缀和的二次扫描法 假设sum[i][j]=a[i][j] for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ sum[i][j]+=sum[i][j-1]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ sum[i][j]+=sum[i-1][j]; } }

第一层循环：对每一行求一维前缀和

=====x-------

=====x-------

=====x-------

此时的sum[i][x]已经累加了该行前面的所有元素

sum[i][j]只代表第 i 行前 j 个元素总和，还不是二维前缀和。

第二层循环：对每一列求一维前缀和

现在sum[i][j]本身已经是第 i 行横向前缀和； 再纵向累加上面一行同列的值。

就得到了二维前缀和

注意查询（x1,y2)(x2,y2)子矩形

ans=sum[x2​][y2​]−sum[x1​−1][y2​]−sum[x2​][y1​−1]+sum[x1​−1][y1​−1]

例题来了：理想的正方形

有一个n×m的整数组成的矩阵，现请你从中找出一个k×k的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

与我们的二次扫描前缀和同源

• 先对每一行，用单调队列求出每行内、长度为 k 的滑动窗口最大值、最小值； 得到两个新矩阵：row_max[i][j]、row_min[i][j]：第 i 行，区间的最大值。
• 再对row_max的每一列做单调队列，窗口大小 k； 得到sq_max[x][y]：左上角对应 (x-k+1,y-k+1) 的正方形最大值。
• 同理对row_min每一列单调队列，得到每个正方形最小值sq_min[x][y]。
• 遍历所有正方形，求。

思路大概是这样的，代码如下：

#include<bits/stdc++.h> #define ll long long const int N=1e3+5; using namespace std; int n,m,k,a[N][N],r_max[N][N],r_min[N][N],ans=0x7fffffff; deque<int> Max,Min; int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ while(!Max.empty()&&Max.front()+k<=j){ Max.pop_front(); } while(!Max.empty()&&a[i][Max.back()]<=a[i][j]){ Max.pop_back(); } Max.push_back(j); while(!Min.empty()&&Min.front()+k<=j){ Min.pop_front(); } while(!Min.empty()&&a[i][Min.back()]>=a[i][j]){ Min.pop_back(); } Min.push_back(j); if(j>=k){ r_min[i][j]=a[i][Min.front()]; r_max[i][j]=a[i][Max.front()]; } } while(!Max.empty()) Max.pop_front(); while(!Min.empty()) Min.pop_front(); } for(int j=k;j<=m;j++){ for(int i=1;i<=n;i++){ while(!Max.empty()&&Max.front()+k<=i){ Max.pop_front(); } while(!Max.empty()&&r_max[Max.back()][j]<=r_max[i][j]){ Max.pop_back(); } Max.push_back(i); while(!Min.empty()&&Min.front()+k<=i){ Min.pop_front(); } while(!Min.empty()&&r_min[Min.back()][j]>=r_min[i][j]){ Min.pop_back(); } Min.push_back(i); if(i>=k){ ans=min(ans,r_max[Max.front()][j]-r_min[Min.front()][j]); } } while(!Max.empty()) Max.pop_front(); while(!Min.empty()) Min.pop_front(); } cout<<ans; }