CF547B - Description
给你个长度为 \(n\) 的序列 \(a\)，对于每个 \(1\le k\le n\)，有 \(n-k+1\) 个中所有长度为 \(k\) 的子串，你需要求出这 \(n-k+1\) 个子串的区间最小值的最大值，即下面式子的值：
\[\max_{l=1}^{n-k+1} \{\ \min_{i=l}^{l+k-1} a_i\ \}
\]
\(1\le n\le 2\times 10^5\)。
CF547B - Solution
首先考虑转化这个问题。假设有 \(l\le i\le r\)，其中 \(a_i\) 是区间 \(\left [ l,r\right ]\) 的最小值，那么 \(a_i\) 一定具有这样一个性质：
- 对于所有 \(j<i\)，若 \(a_i<a_j\)，则有 \(j<l\)。
- 对于所有 \(j>i\)，若 \(a_i<a_j\)，则有 \(j>r\)。
针对这个性质，我们可以在 \(k\) 为定值时将问题转化为一个判定性问题。假设我们目前求出了 \(lft_i\) 和 \(rgt_i\) 来分别表示在 \(i\) 前面第一个小于 \(a_i\) 的数的位置和在 \(i\) 后面的第一个小于 \(a_i\) 的数的位置，那么 \(a_i\) 可以是 $\left [ lft_i+1,rgt_i-1\right ] $ 中任意一个子区间的区间最小值，因此 \(a_i\) 会对所有 \(k\le rgt_i-lft_i-1\) 的答案做出贡献（下面将记作 \(b_i\)）。这里的 \(rgt\) 和 \(lft\) 我们可以使用单调栈 \(O(n)\) 求出，而我们注意到对所有元素从大到小排序，第一个扫到的 \(b_i\) 一定就是最大的，后面不会再被更新，于是我们将 \((b_i,a_i)\) 存为二元组后对 \(a_i\) 从大到小排序。排完序扫一遍，如果每次从上一个更新后的 \(b_{lst}+1\) 开始扫，扫到 \(b_i\)，中间所有答案都赋值为 \(a_i\)。因为所有位置都只会被扫到一次，所以时间复杂度为 \(O(n)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,a[200005],lft[200005],rgt[200005],ava[200005],ans[200005],lst;
stack<int>q,qq;
struct node{int val,av;
}e[200005];
inline bool cmp(node x,node y){if(x.val==y.val){return x.av>y.av;}return x.val>y.val;
}
signed main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){while(!q.empty()&&a[q.top()]>a[i]){rgt[q.top()]=i;q.pop();}q.push(i);}for(int i=n;i>=1;i--){while(!qq.empty()&&a[qq.top()]>a[i]){lft[qq.top()]=i;qq.pop();}qq.push(i);}for(int i=1;i<=n;i++){if(rgt[i]==0){rgt[i]=n+1;}ava[i]=rgt[i]-lft[i]-1;e[i].val=a[i];e[i].av=ava[i];}sort(e+1,e+1+n,cmp);for(int i=1;i<=n;i++){int val=e[i].val;for(int j=e[lst].av+1;j<=e[i].av;j++){lst=i;ans[j]=val;}}for(int i=1;i<=n;i++){cout<<ans[i]<<" ";}return 0;
}