P7988 [USACO21DEC] HILO G 题解

XL4453 · 2022-07-02 22:15:40 · 题解

解题思路：

考虑直接把这个询问的树建立出来。

转化一下就是一个二叉排序树，但是要求询问得早的节点要在询问得节点的上方，也就是一个堆的性质。二叉排序树的性质来自于在询问得到结果之后只会向一个特定的方向走，堆的性质则是来自于询问的顺序的优先级。

然后发现这就是一个笛卡尔树，二叉树权值是题目给出的数的权值，堆的权值是题目给出的数的顺序，直接 O(n) 建立笛卡尔树。

然后考虑什么样的情况下会说出 \text{HILO}，很明显的一种情况是先向左子树走，然后再向右子树走。需要注意的是，当走到一个节点的时候，如果这个节点恰好是询问的那一个，会回答 \text{LO}，也就是说，当向左走之后的一个节点在统计答案的时候需要加一，但是这个加一不会保留到其他子节点。

然后就直接对着这个笛卡尔树遍历一下就好了。

特殊地，询问 0 的时候会一直 \text{HI}，不会出现 \text{HILO}，直接输出 0 就好了。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=2e5+7;
struct str{
    int num,id;
    bool operator < (str x)const{
        return num<x.num;
    }
}p[MAXN];
int n,a[MAXN],stk[MAXN],ls[MAXN],rs[MAXN],ans[MAXN],tot,s;
void dfs(int now,int last){

    if(now==0)return;
    //1 向左 2 向右 
    if(last==1)ans[now]=tot+1;
    else ans[now]=tot;
    dfs(ls[now],1);

    if(last==1)tot++;
    dfs(rs[now],0);
    if(last==1)tot--;
}
int main(){
    scanf("%d",&n);
    printf("0\n");
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i].num);
        p[i].id=i;
    }
    s=p[1].num;
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++){
        a[i]=p[i].id;
    }
    for(int i=1,pos=0,top=0;i<=n;++i){
        pos=top;
        while(pos&&a[stk[pos]]>a[i])pos--;
        if(pos)rs[stk[pos]]=i;
        if(pos<top)ls[i]=stk[pos+1];
        stk[top=++pos]=i;
    }
    dfs(s,-1);

//    for(int i=1;i<=n;i++)
//    printf("%d %d\n",ls[i],rs[i]);

    for(int i=1;i<=n;i++)
    printf("%d\n",ans[i]);
    return 0;
}
/*
先向左再向右算一次，到节点上算一次右 
*/