【Henu ACM Round#17 E】Tree Construction

在这里输入题意

【题解】

做这题之前先要知道二叉排序树的一个性质。
就是它的中序遍历的结果就是这个数组升序排序。
(且每个节点的左边的节点都是比这个节点的值小的,每个节点的右边的节点都是比这个节点的值大的。

则我们把原数组排序。

然后在这里面找到原来数组的a[1]的位置idx;

则1..idx-1这些数字都是a[1]的左子树。

idx+1..n这些数字都是a[1]的右子树。

然后idx的左儿子是什么呢?

肯定就是1..idx-1中在原数组中最早出现的数字。

(因为最早出现,且又比它小。

那么肯定就在根节点的左儿子上了。

那么idx的右儿子呢?

会发现也是idx+1..n中出现最早的数字.

(比它大,且又出现得最早.所以肯定是它的右儿子。

然后就会发现。这是一个递归的过程了。

每个儿子接下来都是这样的。

只需用线段树。维护所有区间内最早出现的数字即可(也即下标最小的数字

【代码】

#include <bits/stdc++.h>

#define ll long long

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const int N = 1e5;

int n,mi[N<<2];

struct abc{

    int id,x;

    bool operator < (const abc &b) const{

        return x < b.x;

    }

}a[N+10];

int tag[N+10],fa[N+10],b[N+10];

void build(int l = 1,int r = n,int rt = 1){

    if (l==r){

        mi[rt] = l;

        return;

    }

    int mid = (l+r)>>1;

    build(lson);

    build(rson);

    int lx = mi[rt<<1],rx = mi[rt<<1|1];

    if (a[lx].id<a[rx].id){

        mi[rt] = lx;

    }else mi[rt] = rx;

}

int query(int L,int R,int l = 1,int r = n,int rt=1){

    if (L<=l && r <= R){

        return mi[rt];

    }

    int mid = (l+r)>>1;

    int id =-1;

    if (L<=mid){

        id = query(L,R,lson);

    }

    if (mid<R){

        int temp1 = query(L,R,rson);

        if (id==-1) id = temp1;

        else if (a[temp1].id<a[id].id) id = temp1;

    }

    return id;

}

void dfs(int l,int r,int f){

    int idx = query(l,r);

    fa[a[idx].id] = f;

    if (idx<r) dfs(idx+1,r,a[idx].id);

    if (l<idx) dfs(l,idx-1,a[idx].id);

}

int main()

{

    ios::sync_with_stdio(0),cin.tie(0);

    #ifdef LOCAL_DEFINE

        freopen("rush.txt","r",stdin);

    #endif // LOCAL_DEFINE

    cin >> n;

    for (int i = 1;i <= n;i++){

        cin >> a[i].x;

        a[i].id = i;

        b[i] = a[i].x;

    }

    sort(a+1,a+1+n);

    build();

    dfs(1,n,0);

    for (int i = 2;i <= n;i++)

        cout << b[fa[i]]<<' ';

    return 0;

}

巴特西

【Henu ACM Round#17 E】Tree Construction

最新文章

热门文章