(Zerojudge) d539: 區間 MAX [終極sparse-table]

https://zerojudge.tw/ShowProblem?problemid=d539

花O(n lg lg n)預處理，花O(1)查詢任意區間的RMQ。

想法：

把lgN東西分成一塊，對每一塊做Sparse-Table，
總複雜度為O( N/(lgN) * lgN * lg(lgN) ) = O(N lg lg N)

再對每一塊的Max做Sparse-Table : O( (N/lgN) * lg(N/lg(N)) ) = O(N)

之後就可以O(1)查詢。想想看吧！

//use sparse table + magic to <O(n lg lg n),O(1)>
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

const int MAX_N = 5e5 +60;
const int MAX_P = 22;
const int MAX_NN = 19;  //lg N
const int MAX_MM = 5;
const int MAX_NNN = 30000+6;
const int MAX_MMM = 16; //lg NN
const int _INF = -2147483648;

int a[MAX_N];
int st_small[MAX_NNN][MAX_MM][MAX_NN];
int st_big[MAX_MMM][MAX_NNN];
int lg2[MAX_N];
int pow2[MAX_P];

void make_st_small(int n,int *a,int st[MAX_MM][MAX_NN]) {
    for (int i=0;n>i;i++) {
        st[0][i] = a[i];
    }
    for (int i=1;MAX_MM>i;i++) {
        for (int j=0;n>j;j++) {
            int r=j+pow2[i-1];
            if (r>=n) r=n-1;
            st[i][j] = max(st[i-1][j],st[i-1][r]);
        }
    }
}

int query_small(int st[MAX_MM][MAX_NN],int l,int r) {
    int dis=(r-l+1);
    return max(st[lg2[dis]][l],st[lg2[dis]][r-pow2[lg2[dis]]+1]);
}

void make_st_big(int n,int *a,int st[MAX_MMM][MAX_NNN]) {
    for (int i=0;n>i;i++) {
        st[0][i] = a[i];
    }
    for (int i=1;MAX_MMM>i;i++) {
        for (int j=0;n>j;j++) {
            int r=j+pow2[i-1];
            if (r>=n) r=n-1;
            st[i][j] = max(st[i-1][j],st[i-1][r]);
        }
    }
}

int query_big(int st[MAX_MMM][MAX_NNN],int l,int r) {
    int dis=(r-l+1);
    return max(st[lg2[dis]][l],st[lg2[dis]][r-pow2[lg2[dis]]+1]);
}

void init() {
    pow2[0]=1;
    for (int i=1;MAX_P>i;i++) {
        pow2[i] = pow2[i-1]*2;
    }
    lg2[1] = 0;
    int id=1;
    for (int i=2;MAX_N>i;i++) {
        if (i==pow2[id]) {
            lg2[i] = lg2[i-1]+1;
            id++;
        }
        else {
            lg2[i] = lg2[i-1];
        }
    }
}

int tmp[MAX_NN];
int aa[MAX_NNN];

int main () {
    init();
    int n;
    scanf("%d",&n);
    for (int i=0;n>i;i++) {
        scanf("%d",&a[i]);
    }
    int small_sz=lg2[n];
    if (small_sz<2) small_sz=2;
    int totgroup=n/small_sz + !(n%small_sz==0);
    for (int i=0;totgroup>i;i++) {
        int t=0;
        for (int j=i*small_sz;i*small_sz+small_sz>j;j++) {
            if (j<n) tmp[t++] = a[j];
            else tmp[t++] = _INF;
        }
        make_st_small(small_sz,tmp,st_small[i]);
        aa[i] = query_small(st_small[i],0,small_sz-1);
    }
    make_st_big(totgroup,aa,st_big);
    int q;
    scanf("%d",&q);
    while (q--) {
        int l,r;
        scanf("%d %d",&l,&r);
        if (l>r) swap(l,r);
        l--;
        r--;
        if (l/small_sz == r/small_sz) {
            //in the same group
            int group_first=(l/small_sz)*small_sz;
            printf("%d\n",query_small(st_small[l/small_sz],l-group_first,r-group_first));
            continue;
        }
        int ans=max(query_small(st_small[l/small_sz],l-(l/small_sz)*small_sz,small_sz-1),
        query_small(st_small[r/small_sz],0,r-(r/small_sz)*small_sz));
        if (l/small_sz +1 == r/small_sz) printf("%d\n",ans);
        else printf("%d\n",max(ans,query_big(st_big,l/small_sz+1,r/small_sz-1)));
    }
}