rmq

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

rmq倍增

struct RMQ{
    static const int maxn=1000,lgmaxn=12;
    static int lg[maxn];
    int mx[maxn][lgmaxn];

    RMQ(){//构造函数
        if(lg[2]!=1){
            for(int i=2;i<maxn;i++){ //因为lg(1)=0
                lg[i]=(i&-i)==i?lg[i-1]+1:lg[i-1];
            }
        }
    }

    void build(int n,int *a){
        for(int i=0;i<=n;i++)mx[i][0]=a[i];
        for(int j=1;j<=lg[n+1];j++)
            for(int i=0;i+(1<<j)-1<=n;i++)
                mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
    }

    int query(int l,int r){
        int k=lg[r-l+1];
        return max(mx[l][k],mx[r-(1<<k)+1][k]);
    }
};

inline int max(int a,int b,int c,int d){return max(max(a,b),max(c,d));}
struct RMQ2{//写的时候下标从0开始，可以当作下标为1开始来使用
    static const int maxn=310,lgmaxn=9;//确保 ( 1<<(lgmaxn-1) ) > maxn
    static int lg[maxn];//log2(x)向下取整
    int mx[maxn][maxn][lgmaxn][lgmaxn];
    RMQ2(){//构造函数不用管的
        if(lg[2]!=1){
            for(int i=2;i<maxn;i++){ //因为lg(1)=0
                lg[i]=(i&-i)==i?lg[i-1]+1:lg[i-1];
            }
        }
    }
    void build(int row,int col,int a[][maxn]){//[0,row],[0,col]
        for(int i=0;i<=row;i++)for(int j=0;j<=col;j++)mx[i][j][0][0]=a[i][j];

        for(int ii=0; (1<<ii)<=row+1; ii++){
            for(int jj=0; (1<<jj)<=col+1; jj++){
                for(int i=0; i+(1<<ii)-1<=row; i++){
                    for(int j=0; j+(1<<jj)-1<=col; j++){
                        if     (ii!=0)mx[i][j][ii][jj]=max(mx[i][j][ii-1][jj],mx[i+(1<<(ii-1))][j][ii-1][jj]);
                        else if(jj!=0)mx[i][j][ii][jj]=max(mx[i][j][ii][jj-1],mx[i][j+(1<<(jj-1))][ii][jj-1]);
                    }
                }
            }
        }
    }
    int query(int r1,int c1,int r2,int c2){
        if(r1>r2)swap(r1,r2);
        if(c1>c2)swap(c1,c2);
        int kr=lg[r2-r1+1], r3=r2+1-(1<<kr);
        int kc=lg[c2-c1+1], c3=c2+1-(1<<kc);
        return max(mx[r1][c1][kr][kc],mx[r1][c3][kr][kc],
                   mx[r3][c3][kr][kc],mx[r3][c1][kr][kc]);
    }
};int RMQ2::lg[maxn];

/******************    on预处理 O1在线查询rmq   *****************/
double Ospace(double n,double blk){
    return pow(2,blk)+2*n/blk+blk+5*n+2*n/blk*ceil(log(2*n/blk)/log(2))+2*n/blk;
}
const int maxn=2e7+21,blk=20,lgmxn=22;//  2^b+2n/b+b    +   2n+2n+n+2n/b*lg+2n/b) = 2^b+5n+b+2n/b(2+lg)
int pre[1<<blk],lg[(maxn<<1)/blk],hi[blk];
void prework(){
    hi[0]=0; for(int i=1;i<blk;i++) hi[i]=hi[i-1]>>1|(1<<(blk-1));
    lg[1]=0; for(int i=2;i*blk<(maxn<<1);i++) lg[i]=lg[i>>1]+1;
    vector<int>sum(1<<blk);// 节约空间
    int b=(1<<blk)-1;
    for(int i=0;i<(1<<blk);i++){
        sum[i^b]=i&1?-1:1;pre[i^b]=0;
        if(sum[i>>1^b]<0) sum[i^b]+=sum[i>>1^b],pre[i^b]=pre[i>>1^b]+1;
    }
}
struct o1rmq{
    int dep[maxn<<1],p[maxn<<1],fst[maxn];
    int rmq[(maxn<<1)/blk][lgmxn],bin[(maxn<<1)/blk];
    int *ls=rmq[0],*rs=ls+maxn;// 内存复用

    void upd(int&x,int y){if(dep[x]>dep[y]) x=y;}
    void build(int n,int*dat){// [0,n)
        int *s=fst,top=0,step=-1;// 内存复用,  使用单调栈为dat建立笛卡尔树
        for(int i=0;i<n;i++){
            ls[i]=rs[i]=-1;
            while(top>0&&dat[i]<dat[s[top]]) ls[i]=s[top--];  // < is min and > is max
            if(top>0)rs[s[top]]=i;
            s[++top]=i;
        }
        dfs(s[1],1,step);//对笛卡尔树进行ett分解，此后ls,rs,栈s将无用处，可以丢弃。

        int exn=(2*n-1+blk-1)/blk;//对ett分块  拓展到blk的倍数
        for(int i=2*n-1;i<exn*blk;i++)dep[i]=dep[i-1]+1;
        for(int i=0;i<exn;i++){
            bin[i]=0;
            for(int j=0;j<blk;j++) if(j==0||dep[i*blk+j]>dep[i*blk+j-1]) bin[i]|=1<<j;
            rmq[i][0]=i*blk+pre[bin[i]];
        }
        for(int j=1;0+(1<<j)<=exn;j++){// 对块进行rmq
            for(int i=0;i+(1<<j)<=exn;i++){//[i,i+1<<j)
                rmq[i][j]=rmq[i][j-1]; upd(rmq[i][j],rmq[i+(1<<(j-1))][j-1]);
            }
        }
    }
    void dfs(int u,int d,int&step){
        p[++step]=u;
        dep[step]=d;
        fst[u]=step;
        if(ls[u]!=-1){
            dfs(ls[u],d+1,step);
            p[++step]=u;
            dep[step]=d;
        }
        if(rs[u]!=-1){
            dfs(rs[u],d+1,step);
            p[++step]=u;
            dep[step]=d;
        }
    }
    int query(int l,int r){//[l,r]  query max value, return idx of min value
        l=fst[l],r=fst[r]; if(l>r)swap(l,r);
        int l1=l/blk,l2=l%blk,r1=r/blk,r2=r%blk;
        if(l1==r1) return p[l+pre[bin[l1]>>l2|hi[blk-(r2-l2+1)]]];
        else{
            int bl=l1*blk==l?l1:l1+1,br=r1*blk+blk-1==r?r1:r1-1;
            int ret=l;
            if(bl<=br) {
                int k=lg[br-bl+1];
                upd(ret,rmq[bl][k]);
                upd(ret,rmq[br-(1<<k)+1][k]);
            }
            if(l1!=bl) upd(ret,l+pre[bin[l1]>>l2|hi[blk-(blk-1-l2+1)]]);
            if(r1!=br) upd(ret,((br+1)*blk)+pre[bin[r1]|hi[blk-(r2-0+1)]]);
            return p[ret];
        }
    }
}rmq;

分块rmq

/******************  O(7n)-O(3) rmq  *****************/
int ospace(int n,int base){return (n>>base)+(n>>base)*ceil(log(n>>base)/log(2))+n*(base+1);}
const int base=5,blk=1<<base,maxn=2e7+7+blk,lgnb=21;
int lg[maxn>>base];
void prework(){
    lg[1]=0; for(int i=2;i*blk<maxn;i++) lg[i]=lg[i>>1]+1;
}
struct normalrmq{
    int rmq[blk][base+1];
    void build(int n,int*a){//[0,n)
        for(int i=0;i<n;i++)rmq[i][0]=a[i];
        for(int j=1;0+(1<<j)-1<n;j++)
            for(int i=0;i+(1<<j)-1<n;i++)
                rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
    }
    int query(int l,int r){
        int k=lg[r-l+1];
        return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
    }
};
struct O7nO3rmq{
    int rmq[maxn/blk][lgnb];
    normalrmq rmq2[maxn/blk];
    void build(int n,int*a){//
        int exn=(n+blk-1)/blk;
        for(int i=0;i<exn;i++){
            rmq2[i].build(blk,a+i*blk);
            rmq[i][0]=rmq2[i].query(0,blk-1);
        }
        for(int j=1;0+(1<<j)-1<exn;j++)
            for(int i=0;i+(1<<j)-1<exn;i++)
                rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
    }
    int query(int l,int r){
        int l1=l/blk,l2=l%blk,r1=r/blk,r2=r%blk;
        if(l1==r1) return rmq2[l1].query(l2,r2);
        else {
            int bl=l1*blk==l?l1:l1+1,br=r1*blk+blk-1==r?r1:r1-1;
            int ret=1<<31;
            if(bl<=br) {
                int k=lg[br-bl+1];
                ret=max(rmq[bl][k],rmq[br-(1<<k)+1][k]);
            }
            if(l1!=bl) ret=max(ret,rmq2[l1].query(l2,blk-1));
            if(r1!=br) ret=max(ret,rmq2[r1].query(0,r2));
            return ret;
        }
    }
}rmq;