[模板题]

本文主要是介绍[模板题]，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一. 倍增

• （1）区间最值

 RMQ 问题（Range Minimum/Maximum Query，区间最值问题）：给定长度为 n 的静态数列，做 m次询问，每次给定 【L,R】，查询区间[L, R]内的最值。

ST 算法两个步骤：

1. 把整个数列分为很多小区间，并提前计算出每个小区间的最值；

2. 对任意一个区间最值查询，找到覆盖它的两个小区间，用两个小区间的最值算出答案。

//区间最大值
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<math.h>

using namespace std;
const int N = 5e5 + 10;
int a[N];
int dp[N][35];  //dp[s][k] 表示 左端点是s，区间长度是2^k【s,s+2^k-1】的最值
int n,q;

void initia()
{
    //初始化
    for(int i = 1; i <= n; i++)dp[i][0] = a[i];
    
    int k_max = log2(n);
    for(int k = 1; k <= k_max; k++)
        for(int s = 1; s + (1 << k) - 1 <= n; s++)
            dp[s][k] = max(dp[s][k-1],dp[s+(1 << (k-1))][k-1]);
}

int check(int l, int r)
{
    int len = r - l + 1;
    int tip = log2(len);
    return max(dp[l][tip],dp[r + 1 - (1<<tip)][tip]);
}

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)cin >> a[i];
    initia();
    int l = 0;
    int r = 0;
    while(q--)   
    {
        cin >> l >> r;
        cout << check(l , r) << endl; 
    } 
    return 0;
}

这篇关于[模板题]的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！