ST 表

luogu 的评测，不用 fastio 容易超时。

这里维护的是最大值。

void solve() {
  int n = read(), m = read();
  vector<int> a(n);
  vector<array<int, 20>> f(n);
  for (int i = 0; i < n; ++i) {
    f[i][0] = a[i] = read();
  }
  // init
  for (int j = 1; j < 20; ++j) {
    for (int i = 0; i < n - (1 << j) + 1; ++i) {
      f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }
  }
  while (m--) {
    int l = read(), r = read();
    --l, --r;
    int l2 = log2(r - l + 1);
    write(max(f[l][l2], f[r - (1 << l2) + 1][l2]));
    putchar('\n');
  }
}