P7988 [USACO21DEC] HILO G

鱼跃于渊 · 2024-10-04 09:45:48 · 题解

解法

考虑先把所有询问的树建出来。
由于询问得到结果后只会进入固定的一个儿子结点，所以这是一颗二叉搜索树。
由于先询问的结点会在后询问的结点上方，所以这又是一个堆。
两者一结合，正是一颗笛卡尔树。
于是我们以下标为堆的权值，原权值为二叉搜索树的权值建出一颗笛卡尔树。

遍历这颗笛卡尔树。
考虑怎样才会说出一个 \texttt{HILO}，显然是在树上先往左儿子走后又往右子树走，统计这种情况的出现次数。
特别的，如果当前结点恰好是询问的那一个，会回答 \texttt{LO}，把这个也统计进答案即可。
时间复杂度 O(n)，可以通过。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define per(i,a,b) for(int i=(a);i<=(b);i++)
#define rep(i,b,a) for(int i=(b);i>=(a);i--)
#define all(x,l,r) &(x)[l],&(x)[r]+1
const int N=2e5+5;
int n,p[N],a[N],ans[N];
int rt,ls[N],rs[N],vis[N];
int top,st[N];
void dfs(int u,int fa,int cnt){
    if(!u) return;
    ans[u]=cnt+(!fa);
    dfs(ls[u],0,cnt);
    dfs(rs[u],1,cnt+(!fa));
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    per(i,1,n) cin>>p[i];
    iota(all(a,1,n),1);
    sort(all(a,1,n),[](const int &x,const int &y){
        return p[x]<p[y];
    });
    st[top=1]=1;
    per(i,2,n){
        while(top&&a[i]<a[st[top]]) ls[i]=st[top--];
        if(top) rs[st[top]]=i;
        st[++top]=i;
    }
    per(i,1,n) vis[ls[i]]++,vis[rs[i]]++;
    per(i,1,n) if(!vis[i]) rt=i;
    dfs(rt,-1,0);
    per(i,0,n) cout<<ans[i]<<'\n';
    return 0;
}