也是拿来复习用的。。

分为预处理和查询。预处理是nlogn的查询时1的,真的是非常快,非常快。
但是他不能修改

然后呢$f[i][j]$表示从$i$点,到$i+2^j$内的最大值。预处理非常简单,用二分的思想做。把$j$减去1,就成功把一个大区间分成两份了。只不过前面的$i$需要被修改达到包含效果。感觉有点像合并石子的鸭子亚哈哈。

接着就是查询操作。还挺简单的,这个没法和预处理一样能通过二分包含。但是$2^{log(x)}>x/2$。
因此只需要把大区间划分为$f[i][log(r-l)],f[r-2^{log(r-l)}+1][log(r-l)]$这两个区间。求一个最大值。

#include<bits/stdc++.h>
#define For(i,l,r) for(int i = l;i<=r;i++)
#define N 100000
using namespace std;
int st[N][30];
int log[N];
int bin[31];
int n;
int m;
void init(){//初始化 
    bin[0]=1;For(i,1,31)bin[i]=bin[i-1]*2;//初始化二的倍数 
    log[0]=-1;For(i,1,n)log[i]=log[i/2]+1;//初始化log值 
    For(i,1,n)cin>>st[i][0];//输入数据 
    For(j,1,log[n]){//预处理,先循环长度,在循环开始点,必须这样 
        For(i,1,n){
            if(j+bin[i]-1<=n){//如果这个区间在合法区间内计算它 
                st[i][j]=max(st[i][j-1],st[i+bin[j-1]][j-1]);
            }
        }
    }
}
int query(int l,int r){//查询函数 
    int j = log[r-l+1];//查询可覆盖的次方值 
    return max(st[l][j],st[r-bin[j]+1][j]);//计算最大值。 
}
int main(){
    cin>>n>>m;
    init();
    For(i,1,m){
        int l,r;
        cin>>l,r;
        cout<<query(l,r);
    }
     
} 
name.com购买域名廉价稳定无需备案 年付.xyz.site.life$3点击购买赠送5$优惠券
racknerd购买无需备案CN2服务器,速度高速稳定节日优惠力度强 节日会推出各种优惠套餐【点击注册】目前推出3H2.5G40GB6T每年$27.80两年$55.60套餐【快来注册
Last modification:May 27th, 2020 at 10:22 pm
觉得好的话就评论,转发,投币。