RMQPOJ3264

Balanced Lineup POJ-3264

DP分析

1. 设A[i]是要求区间最值的数列，F[i, j]表示从第i个数起连续2^j个数中的最大值。（DP的状态）
2. 初状态是F[i,0]=A[i]
3. 状态转移方程F[i, j]=max（F[i，j-1], F[i + 2^(j-1)，j-1]）

void RMQ(int num) //预处理->O(nlogn)
{
    for(int j = 1; j < 20; ++j)    // 这里j的范围根据具体题目数据定义
        for(int i = 1; i <= num; ++i)    // num为数组内整数的个数
            if(i + (1 << j) - 1 <= num)
            {
                maxsum[i][j] = max(maxsum[i][j - 1], maxsum[i + (1 << (j - 1))][j - 1]);
                minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);
            }
}

RMQ算法详解

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;


int maxnum[50010][20];
int minnum[50010][20];
int main()
{
    int num, n, q, i, j, x, y;
    while (~scanf("%d%d", &n, &q))
    {
        for (i = 1; i <= n; i++)
        {
            scanf("%d", &num);
            maxnum[i][0] = minnum[i][0] = num;
        }
        //DP转态转移，如下
        for (j = 1; (1 << j) <= n; j++)
            for (i = 1; i + (1 << j) - 1 <= n; i++)   // 预处理 
            {
                maxnum[i][j] = max(maxnum[i][j - 1], maxnum[i + (1 << (j - 1))][j - 1]);
                minnum[i][j] = min(minnum[i][j - 1], minnum[i + (1 << (j - 1))][j - 1]);
            }

        
        while (q--)
        {
            int ans;
            scanf("%d%d", &x, &y);
            int z = 0;
            while (1 << (z + 1) <= y - x + 1)z++;
ans = max(maxnum[x][z], maxnum[y - (1 << z) + 1][z])//用两个区间中取最大值，两个区间长度相等
                - min(minnum[x][z], minnum[y - (1 << z) + 1][z]);
            printf("%d\n", ans);
        }
    }
    return 0;
}