rmq
2019年8月5日
转移自老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;