# 忠诚

## 样例输入

10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10

2 3 1

## ### ③ c[x]的直接父亲=x+lowbir(x)

uses math;
var
f,a:array[1..2000000] of longint;
n,m,i,x,y,ans:longint; op:char;
procedure buildtree(l,r,k:longint);
var mid:longint;
begin
if l=r then
begin
f[k]:=a[l];
exit;
end;
mid:=(l+r) shr 1;
buildtree(l,mid,k shl 1);
buildtree(mid+1,r,k shl 1+1);
f[k]:=min(f[k shl 1],f[k shl 1+1]);
end;
procedure find(l1,r1,l2,r2,k:longint);
var mid:longint;
begin
if (l1=l2)and(r1=r2) then
begin
ans:=min(f[k],ans);
exit;
end;
mid:=(l2+r2) shr 1;
if r1<=mid then
begin
find(l1,r1,l2,mid,k shl 1);
exit;
end;
if l1>mid then
begin
find(l1,r1,mid+1,r2,k shl 1+1);
exit;
end;
find(l1,mid,l2,mid,k shl 1);
find(mid+1,r1,mid+1,r2,k shl 1+1);
end;
begin
for i:=1 to n do read(a[i]);
buildtree(1,n,1);
for i:=1 to m do
begin
ans:=1000000000;
find(x,y,1,n,1);
if i<>m then write(ans,' ')
else write(ans);
end;
end.


st表
c++
#include<bits/stdc++.h>
const int maxn=200007;
const int maxB=17;
using namespace std;
int n,m,f[maxn][maxB+1],Log[maxn];

int main(){
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++) scanf("%d", &f[i][0]);
Log[1]=0;
for (int i=2; i<=n; i++) Log[i]=Log[i>>1]+1;
for (int j=1; j<=Log[n]; j++)
for (int i=1; i<=n; i++){
f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
while (m--){
int L,R;
scanf("%d%d", &L, &R);
int k=Log[R-L+1];
int ans=min(f[L][k],f[R-(1<<k)+1][k]);
if (m>0) printf("%d ",ans);
else printf("%d\n",ans);
}
return 0;
}