ST 表
用于解决区间可重复贡献问题，需要满足 \(x \text{ 运算符 } x=x\) （如区间最大值：\(\max(x,x)=x\) 、区间 \(\gcd\)：\(\gcd(x,x)=x\) 等），但是不支持修改操作。\(\mathcal O(N\log N)\) 预处理，\(\mathcal O(1)\) 查询。
struct ST {const int n, k;vector<int> in1, in2;vector<vector<int>> Max, Min;ST(int n) : n(n), in1(n + 1), in2(n + 1), k(__lg(n)) {Max.resize(k + 1, vector<int>(n + 1));Min.resize(k + 1, vector<int>(n + 1));}void init() {for (int i = 1; i <= n; i++) {Max[0][i] = in1[i];Min[0][i] = in2[i];}for (int i = 0, t = 1; i < k; i++, t <<= 1) {const int T = n - (t << 1) + 1;for (int j = 1; j <= T; j++) {Max[i + 1][j] = max(Max[i][j], Max[i][j + t]);Min[i + 1][j] = min(Min[i][j], Min[i][j + t]);}}}int getMax(int l, int r) {if (l > r) {swap(l, r);}int k = __lg(r - l + 1);return max(Max[k][l], Max[k][r - (1 << k) + 1]);}int getMin(int l, int r) {if (l > r) {swap(l, r);}int k = __lg(r - l + 1);return min(Min[k][l], Min[k][r - (1 << k) + 1]);}
};