Clasa RMQ

const int NMAX = 1e5 + 5;
int lg2[NMAX];

void compute_lg2(int N) {
  lg2[1] = 0;
  for(int i = 2; i <= N; ++i)
    lg2[i] = lg2[i >> 1] + 1;
}

struct RMQ {
  vector<vector<int>> rmq;

  void compute_rmq(int N) {
    rmq = vector<vector<int>>(N + 1, vector<int>(lg2[N] + 1));
    for(int i = 1; i <= N; ++i)
      rmq[i][0] = a[i].y - a[i].x;
    for(int j = 1; (1 << j) <= N; ++j)
      for(int i = 1; i + (1 << j) - 1 <= N; ++i)
        rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
  }

  int query(int l, int r) {
    int k = lg2[r - l + 1];
    int diff = (r - l + 1) - (1 << k);
    return max(rmq[l][k], rmq[l + diff][k]);
  }
};