【CF 675D】 Tree Construction（离线2分+左右指针）

【CF 675D】 Tree Construction（离线二分+左右指针）

【CF 675D】 Tree Construction（离线二分+左右指针）

During the programming classes Vasya was assigned a difficult problem. However, he doesn't know how to code and was unable to find the solution in the Internet, so he asks you to help.

You are given a sequence a, consisting of n distinct integers, that is used to construct the binary search tree. Below is the formal description of the construction process.

First element a1 becomes the root of the tree.
Elements a2, a3, ..., an are added one by one. To add element ai one needs to traverse the tree starting from the root and using the following rules:
1. The pointer to the current node is set to the root.
2. If ai is greater than the value in the current node, then its right child becomes the current node. Otherwise, the left child of the current node becomes the new current node.
3. If at some point there is no required child, the new node is created, it is assigned value ai and becomes the corresponding child of the current node.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the length of the sequence a.

The second line contains n distinct integers ai (1 ≤ ai ≤ 109) — the sequence a itself.

Output

Output n - 1 integers. For all i > 1 print the value written in the node that is the parent of the node with value ai in it.

Examples

input
3
1 2 3

output
1 2

input
5
4 2 3 1 6

output
4 2 2 4

Note

Picture below represents the tree obtained in the first sample.

$【CF 675D】 Tree Construction（离线2分+左右指针）$

Picture below represents the tree obtained in the second sample.

$【CF 675D】 Tree Construction（离线2分+左右指针）$

题目大意：建立二叉查找树。添加n个结点，输出添加第2~n个结点时对应的父节点值(第1个点是根无父节点故不输出

首先要找到一个结论:对于已添加第1~(i-1)个结点的树，添加第i个结点v时，父亲一定是之前添加的值最接近v的点。即min(|u-v|)的那个u

这样会出现u < v或者u > v（及左边最靠近v和右边最靠近v的）两种一定是选择最晚出现的u来作为v的父亲。

因为对于两个u此时已经加入到树中，而且在没有v之前，uL与uR是相邻(连)的。及其中一个为另一个父亲

其实也就是较早出现的为较晚出现的那个点的父亲。

在线处理的话，如果能很快插入的话，保证序列有序，每次插入一个点前，二分出该点的左右邻点，找出其中最晚出现的，即为该点父亲。

我用的vector超时了，看他们有用set过的。。。没试

后来想到秃头，想出一个离线处理的方法。

先把所有点存下来，并按点值从小到大排序，然后去个重。同时，每个点记录最早出现的时刻，还有左右邻点。

然后从第n次加入到第2次加入的点遍历(读取的时候预先备份一下即可

二分找到这个点，然后比较下左右邻点，选取所需要的即可。

如果找某个点时，发现再往前没有该点，把他左右邻点链接即可。即为将该点扣去。

代码如下:

#include <bits/stdc++.h>
#define LL long long

using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-8;

struct Node
{
    int x,mn,mx,l,r;
    bool operator < (const struct Node a)const
    {
        return x < a.x;
    }
};

Node nd[100100];
int x[100100];
int ans[100100];
int tp = 0;

int main()
{
    int n,l,r,pos;

    scanf("%d",&n);

    for(int i = 0; i < n; ++i)
    {
        scanf("%d",&x[i]);
<span style="white-space:pre">	</span>nd[i].x = x[i];
        nd[i].mn = nd[i].mx = i;
    }

    sort(nd,nd+n);

    for(int i = 0; i < n; ++i)
    {
        if(tp == 0 || nd[i].x != nd[tp-1].x)
        {
            nd[tp++] = nd[i];
            nd[tp-1].l = tp-2;
            nd[tp-1].r = tp;
        }
        else
        {
            nd[tp-1].mn = min(nd[tp-1].mn,nd[i].mn);
            nd[tp-1].mx = min(nd[tp-1].mn,nd[i].mx);
        }
    }

    for(int i = n-1; i > 0; --i)
    {
        l = 0, r = tp-1;

        while(l <= r)
        {
            int mid = (l+r)>>1;
            if(nd[mid].x == x[i])
            {
                pos = mid;
                break;
            }
            else if(nd[mid].x > x[i]) r = mid-1;
            else l = mid+1;
        }

        if(nd[pos].l == -1) ans[i] = nd[nd[pos].r].x;
        else if(nd[pos].r == tp) ans[i] = nd[nd[pos].l].x;
        else if(nd[nd[pos].r].mn > nd[nd[pos].l].mn) ans[i] = nd[nd[pos].r].x;
        else ans[i] = nd[nd[pos].l].x;

        if(nd[pos].mn == i)
        {
            nd[nd[pos].l].r = nd[pos].r;
            nd[nd[pos].r].l = nd[pos].l;
        }
    }

    for(int i = 1; i < n; ++i)
    {
        if(i != 1) putchar(' ');
        printf("%d",ans[i]);
    }

    return 0;
}

【CF 675D】 Tree Construction（离线2分+左右指针）

相关推荐