Java教程

[模板题]

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

一. 倍增

  • (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;
}

 

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