题意：给定一个长为$n$的序列，定义$f(x)$表示所有(长为$x$的区间最小值)的最大值，求$f(1)$~$f(n)$。
看好多人都用并查集做的，然而我并不想写……既然品酒大会可以后缀数组+并查集也可以直接用后缀树递推，那这个问题直接上树再递推也行吧……
跟RMQ有关的一个树形结构就是笛卡尔树，那么我们构建笛卡尔树后自底向上递推一遍即可，对每个节点更新它对应区间长度的答案，最后根据$f(x)\ge f(x+1)$更新一遍所有的$f$即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
void bfs();
int n,a[maxn],f[maxn],root,lc[maxn]={},rc[maxn]={},s[maxn],top=,q[maxn],size[maxn]={};
int main(){
freopen("sky_seq.in","r",stdin);
freopen("sky_seq.out","w",stdout);
memset(f,-,sizeof(f));
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
s[++top]=root=;
for(int i=;i<=n;i++){
s[top+]=;
while(a[i]<a[s[top]])top--;
if(top)rc[s[top]]=i;
else root=i;
lc[i]=s[top+];
s[++top]=i;
}
bfs();
for(int i=n;i;i--)f[i]=max(f[i],f[i+]);
for(int i=;i<=n;i++)printf("%d ",f[i]);
return ;
}
void bfs(){
int x,head=,tail=;
q[tail++]=root;
while(head!=tail){
x=q[head++];
size[x]=;
if(lc[x])q[tail++]=lc[x];
if(rc[x])q[tail++]=rc[x];
}
for(int i=n;i;i--){
x=q[i];
size[x]+=size[lc[x]]+size[rc[x]];
f[size[x]]=max(f[size[x]],a[x]);
}
}
lyc说这个题是从CF上搬过来的，然而他也忘了是哪道题了……麻烦知道的dalao在评论里告诉我一声……