首页 > 代码库 > 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