RMQ板子

对于RMQ这种静态最值询问, 用线段树的话查询过慢, 一般用ST表预处理后O(1)查询, 下以最大值查询为例, 这里假定$n$不超过5e5

void init(int *a, int n) {

    Log[0] = -1;

    REP(i,1,n) f[0][i] = a[i], Log[i]=Log[i>>1]+1;

    REP(j,1,19) for (int i=0;i+(1<<j-1)-1<=n; ++i) {

        f[j][i] = max(f[j-1][i],f[j-1][i+(1<<j-1)]);

    }

}

int RMQ(int l, int r) {

    if (l>r) return -INF;

    int t = Log[r-l+1];

    return max(f[t][l],f[t][r-(1<<t)+1]);

}

若需要求最大值的下标, 可以这样写

void init(int *a, int n) {

    Log[0]=-1;

    REP(i,1,n) f[0][i] = i, Log[i]=Log[i>>1]+1;

    REP(j,1,19) for (int i=0; i+(1<<j)-1<=n; i++) {

        int x = f[j-1][i], y = f[j-1][i+(1<<(j-1))];

        f[j][i]=a[x]>a[y]?x:y;

    }

}

int RMQ(int l, int r) {

    if (l>r) return -1;

    int k = Log[r-l+1];

    int x = f[k][l], y = f[k][r-(1<<k)+1];

    return a[x]>a[y]?x:y;

}

巴特西

RMQ板子

最新文章

热门文章