P1377 [TJOI2011]树的序题解

题面

这个题相当于是把每个数的值作为 \(x_i\)，在原序列中的位置为 \(y_i\)，建出笛卡尔树，直接输出先序遍历（字典序最小）即可。

点击查看代码

#include<iostream>#include<cstdio>using namespace std;inline int rd(){int res=0;char c=getchar();for(;!isdigit(c);c=getchar());for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');return res;}const int N=1e5+13;int n,a[N],s[N],top,L[N],R[N];void dfs(int u){printf("%d ",u);if(L[u]) dfs(L[u]);if(R[u]) dfs(R[u]);}int main(){n=rd();int rt=0;for(int i=1,x;i<=n;++i) x=rd(),a[x]=i;for(int i=1;i<=n;++i){int pos=top;while(pos&&a[s[pos]]>a[i]) --pos;if(pos) R[s[pos]]=i;if(pos<top) L[i]=s[pos+1];s[top=(++pos)]=i;}dfs(s[1]);return 0;}

免责声明：本网信息来自于互联网，目的在于传递更多信息，并不代表本网赞同其观点。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，并请自行核实相关内容。本站不承担此类作品侵权行为的直接责任及连带责任。如若本网有任何内容侵犯您的权益，请及时联系我们，本站将会在24小时内处理完毕。