UVa548

UVa548

ポストオーダーの最後に登場する頂点でインオーダーを分割する。
このコードより簡単な実装or解法がある気がする。

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>

using namespace std;

const int N = 10000 + 1;
pair<int, int> node[N];

int I[N];
int P[N];

int idx[N];
int rev[N];

const int inf = 1 << 28;

namespace RMQ {
  const int MAX_N = N;
  int n, dat[4 * MAX_N - 1];

  void init(int _n = MAX_N)
  {
    n = 1;
    while (n < _n) n *= 2;
    for (int i = 0; i < 2 * n - 1; ++i) {
      dat[i] = inf;
    }
  }

  void update_(int k, int a)
  {
    k += n - 1;
    dat[k] = a;
    while (k > 0) {
      k = (k - 1) / 2;
      dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
    return ;
  }

  int query_(int a, int b, int k = 0, int l = 0, int r = RMQ::n)
  {
    if (r <= a || b <= l) return inf;
    if (a <= l && r <= b) return dat[k];
    else {
      int v1 = query_(a, b, k * 2 + 1, l, (l + r) / 2);
      int v2 = query_(a, b, k * 2 + 2, (l + r) / 2, r);
      return min(v1, v2);
    }
  }
  void update(int k, int a)
  {
    update_(k, -1 * a);
    return ;
  }

  int query(int a, int b, int k = 0, int l = 0, int r = RMQ::n)
  {
    return -1 * query_(a, b, k, l, r);
  }
};

int f(int num[], string s)
{
  istringstream iss(s);
  string t;
  int i;
  for (i = 0; iss >> t; ++i) {
    num[i] = atoi(t.c_str());
  }
  return i;
}

int rec(int begin, int end)
{
  if (begin == end) return -1;
  if (begin + 1 == end) return I[begin];

  int root = RMQ::query(begin, end);
  root = rev[P[root]];

  int a = rec(begin, root);
  int b = rec(root + 1, end);
  node[I[root]] = make_pair(a, b);

  return I[root];
}

pair<int, int> visit(int n, int sum)
{
  if (node[n] == make_pair(-1, -1)) {
    return make_pair(sum, n);
  }

  pair<int, int> mn = make_pair(1 << 28, 1 << 28);
  if (node[n].first != -1) {
    mn = min(mn, visit(node[n].first, sum + node[n].first));
  }
  if (node[n].second != -1) {
    mn = min(mn, visit(node[n].second, sum + node[n].second));
  }
  return mn;
}

int main(void)
{
  string in, post;
  while (getline(cin, in) && getline(cin, post)) {
    fill(node, node + N, make_pair(-1, -1));

    int size;
    size = f(I, in);
    size = f(P, post);

    for (int i = 0; i < size; ++i) {
      idx[P[i]] = i;
      rev[I[i]] = i;
    }

    RMQ::init();
    for (int i = 0; i < size; ++i) {
      RMQ::update(i, idx[I[i]]);
    }

    const int root = rec(0, size);
    cout << visit(root, root).second << endl;
  }
  return 0;
}