leetcode-go/poj/3264.balanced-lineup/main.cc

#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 50000;
const int INF = 1 << 30;

struct TNode {
  int min;
  int max;
  int beg;
  int end;
  TNode *l;
  TNode *r;
  int mid() { return beg + (end - beg) / 2; }
};

TNode tree[2 * N];
int tid = 0;

TNode *build_tree(TNode *root, int beg, int end) {
  root->beg = beg;
  root->end = end;
  root->max = -INF;
  root->min = INF;
  if (beg != end) {
    root->l = build_tree(&tree[tid++], beg, root->mid());
    root->r = build_tree(&tree[tid++], root->mid() + 1, end);
  }
  return root;
}

void insert(int key, int val) {
  TNode *root = &tree[0];
  while (root->beg != root->end) {
    root->min = min(root->min, val);
    root->max = max(root->max, val);
    if (key <= root->mid())
      root = root->l;
    else
      root = root->r;
  }
  root->min = val;
  root->max = val;
}

pair<int, int> query(TNode *root, int beg, int end) {
  if (root->beg == beg && root->end == end) return {root->max, root->min};
  if (root->mid() < beg) return query(root->r, beg, end);
  if (end <= root->mid()) return query(root->l, beg, end);
  pair<int, int> pl = query(root->l, beg, root->mid());
  pair<int, int> pr = query(root->r, root->mid() + 1, end);
  return {max(pl.first, pr.first), min(pl.second, pr.second)};
}

int main() {
  int n, q, h;
  scanf("%d %d", &n, &q);
  build_tree(&tree[tid++], 1, n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &h);
    insert(i, h);
  }
  for (int i = 0, s, e; i < q; i++) {
    scanf("%d %d", &s, &e);
    pair<int, int> p = query(&tree[0], s, e);
    printf("%d\n", p.first - p.second);
  }
  return 0;
}