ST表

const int N = ${1:5e5} + 5;
int lg[N];

void init() {
  lg[0] = -1;
  for (int i = 1; i < N; i++) {
    lg[i] = lg[i >> 1] + 1;
  }
}

struct ST {
  int n;
  vector<vector<int>> st;
  void init(vector<int> &c) {
    n = c.size();
    st.assign(n, vector<int>(lg[n] + 1, 0));
    for (int i = 0; i < n; i++) {
      st[i][0] = c[i];
    }
    for (int j = 1; j <= lg[n]; j++) {
      int pj = 1 << j - 1;
      for (int i = 0; i + pj < n; i++) {
        st[i][j] = max(st[i][j - 1], st[i + pj][j - 1]);
      }
    }
  }
  int query(int l, int r) {
    int d = r - l + 1;
    int q = lg[d];
    return max(st[l][q], st[r - (1 << q) + 1][q]);
  }
};
// 下标应为从 0 开始
// 千万记得 init()