Problem - D - Codeforces
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.

　 $2$ 分木の挿入する順番が与えられる．挿入した時の親の番号を答える．
愚直に木を構成すると線のような木の場合に $O(n ^2)$ となるので間に合わない．区間をsetで管理すると次に挿入する場所が $logn$ で持ってこれるので，全体で $O(n logn)$ となる．map( $l, r$ )に区間 $[l, r]$ の親を持っておくようにした．

sample2でどのように動くかをメモしておく．(書いておかないと絶対忘れる．．．)

Sample 2

$5$
$4\ 2\ 3\ 1\ 6\$

手順，挿入する数，挿入する区間 $\to$ 挿入した結果と書いてみた．

$\begin{eqnarray} insert \ \ (4) \ \ [-\infty, \infty] \ \ &\to& \ \ [-\infty, 4], [4, \infty] \\ insert \ \ (2) \ \ [-\infty,\ \ 4] \ \ &\to& \ \ [-\infty, 2], [2, 4], [4, \infty] \\ insert \ \ (3) \ \ [\,\ \ \ \ 2,\ \ 4] \ \ &\to& \ \ [-\infty, 2], [2, 3], [3, 4], [4, \infty] \\ insert \ \ (1) \ \ [-\infty,\ \ 2] \ \ &\to& \ \ [-\infty, 1], [1, 2], [2, 3], [3, 4], [4, \infty] \\ insert \ \ (6) \ \ [\,\ \ \ \ 4,\infty] \ \ &\to& \ \ [-\infty, 1], [1, 2], [2, 3], [3, 4], [4, 6], [6, \infty] \\ \end{eqnarray}$

後は区間 $[l, r]$ のmapに入っている値を答えて， $[l, v[i]], [v[i], r]$ に $v[i]$ を入れておく．

Code

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

map<P, int> m;

int main() {
  int n;
  cin >> n;

  vector<int> v(n);
  rep(i, n) cin >> v[i];

  vector<int> ans;

  set<int> st;
  st.insert(INF);
  st.insert(-INF);
  st.insert(v[0]);

  m[mp(-INF, v[0])] = v[0];
  m[mp(v[0], INF)] = v[0];

  REP(i, 1, n) {
      set<int>::iterator ite = st.upper_bound(v[i]);
      int r = *ite;
      ite--;
      int l = *ite;

      ans.push_back(m[mp(l, r)]);

      m[mp(l, v[i])] = v[i];
      m[mp(v[i], r)] = v[i];
      st.insert(v[i]);
  }

  rep(i, ans.size()) {
      cout << ans[i];

      if(i == ans.size()-1) cout << endl;
      else cout << " ";
  }


  return 0;
}

ry0u_ydのblog

Codeforces353-div2D Tree Construction

Problem - D - Codeforces

Sample 2

Code