首页 > 代码库 > CodeForces 675D Tree Construction
CodeForces 675D Tree Construction
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-‘0‘; c=getchar();}}const int maxn=100010;struct X{int x,id;}s[maxn];int n,sz,ans[maxn],a[maxn];struct Node { int id,L,R; }node[maxn];bool cmp(X a,X b){ return a.x<b.x;}bool cmp1(X a,X b){ return a.id<b.id;}int dp[maxn][30];void RMQ_init(){ for(int i=0;i<n;i++) dp[i][0]=i; for(int j=1;(1<<j)<=n;j++) for(int i=0;i+(1<<j)-1<n;i++){ if(a[dp[i][j-1]]<a[dp[i+(1<<(j-1))][j-1]]) dp[i][j]=dp[i][j-1]; else dp[i][j]=dp[i+(1<<(j-1))][j-1]; }}int RMQ(int L,int R){ int k=0; while((1<<(k+1))<=R-L+1) k++; if(a[dp[L][k]]<a[dp[R-(1<<k)+1][k]]) return dp[L][k]; return dp[R-(1<<k)+1][k];}void build(int L,int R,int fa,int f){ int pos=RMQ(L-1,R-1); pos++; if(fa!=-1) { if(f==0) node[fa].L=s[pos].id; else node[fa].R=s[pos].id; } if(pos-1-L>=0) build(L,pos-1,s[pos].id,0); if(R-(pos+1)>=0) build(pos+1,R,s[pos].id,1);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&s[i].x),s[i].id=i; sort(s+1,s+1+n,cmp); for(int i=1;i<=n;i++) a[i-1]=s[i].id; RMQ_init(); build(1,n,-1,0); sort(s+1,s+1+n,cmp1); for(int i=1;i<=n;i++) ans[node[i].L]=s[i].x, ans[node[i].R]=s[i].x; for(int i=2;i<=n;i++) printf("%d ",ans[i]); return 0;}
CodeForces 675D Tree Construction
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。