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;