RMQ（二进制方法）

2014-11-02 | Tech

问题描述

已知数组 a 以及若干个查询 $(x, y)$，求 $a[x..y]$ 之间的最小值。

分析

不难发现：若取 t 使得$2^t\leq y-x+1$且$2^{t+1}>y-x+1$，则有：

$$[x, x+t]\bigcup[y-t+1,y]=[x,y]$$

运用二进制的思想，我们只需预处理出 $i..i+2^k-1$ 之间的最小值，即可快速完成查询。设 $dp[i][j]$ 为 $i..i+2^j-1$ 之间的最小值，则有：

$$dp[i][j]=min(dp[i][j-1],dp[i+2^{j-1}][j-1])$$

Code

var
    a: array [1..100000] of longint;
    dp: array [1..100000, 0..20] of longint;
    n, i: longint;

function min(x, y: longint): longint;
begin
    if x < y then exit(x) else exit(y);
end;

procedure init;
var
    i, j: longint;
begin
    for i := 1 to n do dp[i, 0] := a[i];
    j := 1;
    while 1<<j-1<=n do
    begin
        for i := 1 to n-1<<(j-1) do
            dp[i, j] := min(dp[i, j-1], dp[i+1<<(j-1), j-1]);
        inc(j);
    end;
end;

function query(x, y: longint): longint;
var
    t: longint;
begin
    t := 0;
    while (1<<(t+1)<=y-x+1) do inc(t);
    query := min(dp[x][t], dp[y-(1<<t)+1][t]);
end;

var
    x, y: longint;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(n);
    for i := 1 to n do read(a[i]);
    init;
    while not eof do
    begin
        read(x, y);
        writeln(query(X, y));
    end;

    close(input); close(output);
end.

作者：hsfzxjy
链接：
许可：CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途，非商业转载请注明出处。

NOIP

OOPS!

A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.