#1068 : RMQ-ST算法
10000ms
1000ms
256MB
描述
小Hi和小Ho在美國旅行了相當長的一段時間之後，終于準備要回國啦！而在回國之前，他們準備去超市采購一些當地特産——比如漢堡（大霧）之類的回國。
但等到了超市之後，小Hi和小Ho發現者超市擁有的商品種類實在太多了——他們實在看不過來了！于是小Hi決定向小Ho委派一個任務：假設整個貨架上從左到右拜訪了N種商品，并且依次标号為1到N，每次小Hi都給出一段區間[L, R]，小Ho要做的是選出标号在這個區間内的所有商品重量最輕的一種，并且告訴小Hi這個商品的重量，于是他們就可以毫不費勁的買上一大堆東西了——多麼可悲的選擇困難症患者。
（雖然說每次給出的區間仍然要小Hi來進行決定——但是小Hi最終機智的選擇了使用随機數生成這些區間！但是為什麼小Hi不直接使用随機數生成購物清單呢？——問那麼多做什麼！）
提示一：二分法是宇宙至強之法！（真的麼？）
提示二：線段樹不也是二分法麼？
輸入
每個測試點（輸入檔案）有且僅有一組測試資料。
每組測試資料的第1行為一個整數N，意義如前文所述。
每組測試資料的第2行為N個整數，分别描述每種商品的重量，其中第i個整數表示标号為i的商品的重量weight_i。
每組測試資料的第3行為一個整數Q，表示小Hi總共詢問的次數。
每組測試資料的第N+4~N+Q+3行，每行分别描述一個詢問，其中第N+i+3行為兩個整數Li, Ri，表示小Hi詢問的一個區間[Li, Ri]。
對于100%的資料，滿足N<=10^6，Q<=10^6, 1<=Li<=Ri<=N，0<weight_i<=10^4。
輸出
對于每組測試資料，對于每個小Hi的詢問，按照在輸入中出現的順序，各輸出一行，表示查詢的結果：标号在區間[Li, Ri]中的所有商品中重量最輕的商品的重量。
樣例輸入
10
7334
1556
8286
1640
2699
4807
8068
981
4120
2179
5
3 4
2 8
2 4
6 8
7 10
樣例輸出
1640
981
1556
981
981
二分原理---
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int st[1000100][25];
int main()
{
int n,q;
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&st[i][0]);
for (int j=2,p=1;j<=n;j*=2,p++)
for (int i=1;i+j-1<=n;i++)
{
st[i][p]=min(st[i][p-1],st[i+j/2][p-1]);
}
scanf("%d",&q);int a,b,p,ans;
while (q--)
{
int c=0,i;
scanf("%d%d",&a,&b);
for (i=2;i<=b-a+1;i*=2)
c++;
ans=min(st[a][c],st[b-i/2+1][c]);
printf("%d\n",ans);
}
return 0;
}