ST表

ST表

//使用注意事项：记得调用st.init()，另外记得把aaa[i]换成一个正确的值
struct ST {
    int f[22][N], g[22][N];//将f[N][22]写成f[22][N]可以提升效率，若数组定义为f[n][22],则f[i][j]表示需要查询的数组从下标i到下标i+2^(j-1)的最大值，g[i][j]表示需要查询的数组从下标i到下标i+2^(j-1)的最小值
    int lg[N];
    void init() {
        lg[1] = 0;
        for (int i = 2; i <= n; i++)
            lg[i] = lg[i / 2] + 1;
        for (int i = 1; i <= n; i++) {
            f[0][i] = aaa[i];
            g[0][i] = aaa[i];
        }
        for (int j = 1; j <= 20; j++) {
            for (int i = 1; i + (1LL << j) - 1 <= n; i++) {
                f[j][i] = max(f[j - 1][i], f[j - 1][i + (1LL << (j - 1))]);  //求最大
                g[j][i] = min(g[j - 1][i], g[j - 1][i + (1LL << (j - 1))]);  //求最小
            }
        }
    }
    int ask_max(int l, int r) {
        if (l > r)
            swap(l, r);
        int len = lg[r - l + 1];
        int ans = max(f[len][l], f[len][r - (1 << len) + 1]);
        return ans;
    }
    int ask_min(int l, int r) {
        if (l > r)
            swap(l, r);
        int len = lg[r - l + 1];
        int ans = min(g[len][l], g[len][r - (1 << len) + 1]);
        return ans;
    }
};

int n, q, lg[N];
int a[N], f[22][N], ans;  //将f[N][22]写成f[22][N]可以提升效率
//若数组定义为f[n][22],则f[i][j]表示需要查询的数组从下标i到下标i+2^(j-1)的最值
void build() {
    lg[1] = 0;
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i / 2] + 1;
    for (int i = 1; i <= n; i++) {
        f[0][i] = a[i];
    }
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);  //求最大
        }
    }
}
int query(int l, int r) {
    if (l > r)
        swap(l, r);
    int len = lg[r - l + 1];
    int ans = max(f[len][l], f[len][r - (1 << len) + 1]);
    return ans;
}

const int N = 1e6 + 10;
int n, q, lg[N];
int a[N], f[22][N], ans;//将f[N][22]写成f[22][N]可以提升效率
//若数组定义为f[n][22],则f[i][j]表示需要查询的数组从下标i到下标i+2^(j-1)的最值
void pre(int n) {
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
}
void solve() {
    scanf("%d%d", &n, &q);//长度为n的数组，q次查询
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        f[0][i] = a[i];
    }
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);//求最大
        }
    }
    pre(n);
    for (int i = 1; i <= q; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        if (l > r) swap(l, r);
        int len = lg[r - l + 1];
        ans = max(f[len][l], f[len][r - (1 << len) + 1]);
        printf("%d\n", ans);
    }
}