bzoj1699

st表

我还不会st表

f[i][j]表示[i,i+2^j)区间的最值

构造就像lca一样f[i][j]=f[i][j-1] f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]) 表示[i+2^(j-1)) [i+2^(j-1), i+2^j)

然后查询找出一个2的幂，从头和尾覆盖查询区间，max(mx[l][x],mx[r-2^x+1][x]) 这样覆盖了整个区间

#include<bits/stdc++.h>
using namespace std;
const int N = 50010;
int n, q;
int mx[N][24], mn[N][24], a[N];
void query(int l, int r)
{
    int x = log(r - l + 1) / log(2);
    int x1 = max(mx[l][x], mx[r - (1 << x) + 1][x]);
    int x2 = min(mn[l][x], mn[r - (1 << x) + 1][x]);
    printf("%d
", x1 - x2);
}
int main()
{
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; ++i)
    {
        int x;
        scanf("%d", &a[i]);
        mx[i][0] = a[i];
        mn[i][0] = a[i];
    } 
    for(int i = 1; i <= 23; ++i)
        for(int j = n; j; --j) 
        {
            mn[j][i] = mn[j][i - 1];
            mx[j][i] = mx[j][i - 1];
            if(j + (1 << (i - 1)) <= n)
            {
                mx[j][i] = max(mx[j][i], mx[j + (1 << (i - 1))][i - 1]);
                mn[j][i] = min(mn[j][i], mn[j + (1 << (i - 1))][i - 1]);
            }
        }
    while(q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        query(l, r);
    }    
    return 0;
}