题解 | 信息学奥赛一本通 - 数列区间最大值

本题是经典的静态序列区间最大值问题 (RMQ)，可以用ST表等数据结构解决

其中ST表较为优秀，它只需要Onlogn的预处理时间，查询为O1

我们令st[i][j]表示序列的第i个元素到中的最大值，然后从1到logn遍历j，预处理所有的st

其中，这是一个倍增的过程

那么接下来对于每个询问区间，都可以有两个st表中存下来的区间合并来求出最值。

#include<iostream>
#include<cstdio>
using namespace std; 
const int maxn=1e5+10;
int n,m;
const int ch_top=4e7;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
int mx[maxn][22];
int lg[maxn];
int max(int a,int b){return a>b?a:b;}
inline int query(int l,int r)
{
    int k=lg[r-l+1];
    return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
int main()
{
    lg[0]=-1;for(int i=1;i<maxn;i++)lg[i]=lg[i>>1]+1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&mx[i][0]);
    for(int j=1;j<=22;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
    while(m--){int l,r;scanf("%d%d",&l,&r);printf("%d\n",query(l,r));}
}

另外，区间RMQ有O(n)-O(1)的解法，为笛卡尔树或者分块st表。

//笛卡尔树
//题目链接 https://www.luogu.org/problem/P3793
#include<bits/stdc++.h>

const int maxn=2e7+10;
int n,m,a[maxn],ls[maxn],rs[maxn],stk[maxn],tp=0,rt,RAND;

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

inline int que(int l,int r){
    int x=stk[1];
    while(1){
        if(l<=x&&x<=r) return a[x];
        if(x>r)x=ls[x];
        else x=rs[x];
    }
}

inline void Swap(int &l,int &r){
    l^=r;r^=l,l^=r;
}

int main(){
    scanf("%d%d%d",&n,&m,&RAND);srand(RAND);
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++){
        while(tp&&a[stk[tp]]<a[i]) ls[i]=stk[tp--];
        rs[stk[tp]]=i;stk[++tp]=i;
    }
    unsigned long long ans=0;
    while(m--){
        int l=read()%n+1,r=read()%n+1;
        if(l>r) Swap(l,r);
        ans+=que(l,r);
    }
    return printf("%llu\n",ans),0;
}

// 分块ST表
#include<bits/stdc++.h>

namespace GenHelper{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
inline void srand(unsigned x){using namespace GenHelper;z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
inline int read(){
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

const int maxn=2e7+10;
const int SIZ=4750,NUM=maxn/SIZ+10;
int n,m,s[maxn];
int st[15][NUM],lg2[NUM];
unsigned long long ans;

inline void Swap(register int &l,register int &r){
    int t=l;
    l=r;r=t;
}
inline int Min(register int a,register int b){
    return a<b?a:b;
}

inline int Max(register int a,register int b){
    return a>b?a:b;
}

int lmax[maxn],rmax[maxn];
int l[NUM],r[NUM],pos[maxn];
unsigned RAND;

inline int que(register int l,register int r){
    if(l>=r) return 0;
    int t=lg2[r-l];
    return Max(st[t][l],st[t][r-(1<<t)]);
}


int main(){
    scanf("%d%d%u",&n,&m,&RAND);srand(RAND);
    for(int i=1;i<=n;i++) s[i]=read(),pos[i]=i/SIZ+1;
    const int B=pos[n];
    lg2[0]=-1;
    for(register int i=1;i<=B;++i)lg2[i]=lg2[i>>1]+1;
    for(register int i=1;i<=B;i++){
        l[i]=(i-1)*SIZ;r[i]=l[i]+SIZ-1;
    }
    l[1]=1,r[B]=n;
    for(register int i=1,now=1,lst=0;i<=n;i++){
        lmax[i]=lst=Max(s[i],lst);
        if(i>=r[now]) st[0][now]=lmax[i],lst=0,++now;
    }
    for(register int i=n,now=B,lst=0;i>=0;i--){
        rmax[i]=lst=Max(s[i],lst);
        if(i<=l[now]) lst=0,now--;
    }
    for(register int i=1,pw=1;i<=14;i++,pw<<=1){
        for(register int j=1;j<=B;j++)
            st[i][j]=Max(st[i-1][j],st[i-1][Min(j+pw,B)]);
    }
    while(m--){
        register int l=read()%n+1,r=read()%n+1;
        if(l>r) Swap(l,r);
        register int pl=pos[l],pr=pos[r];
        if(pl^pr) ans+=Max(Max(rmax[l],lmax[r]),que(pl+1,pr));
        else {
            register int res=0;
            for(register int i=l;i<=r;i++)
                res=Max(res,s[i]);
            ans+=res;
        }
    }
    printf("%llu\n",ans);
    return 0;
}