问题描述

已知数组 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.