一、寫在前面
剛開始學習一個新玩意的時候當然是寫一個模闆了，對于靜态的區間最值查詢，ST表是個好方法。這道模闆題強調了“最大資料時限隻有0.8s，資料強度不低，請務必保證你的每次查詢複雜度為 O(1) O(1)”，下面就用實際經曆“解釋一下”。
先貼代碼。
二、代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e6+10;
vector<int> a;
int d[maxn][25];
int n,m,p;
inline int read(){
char ch=getchar();
int ans=0,f=1;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ans=ans*10+ch-'0';
ch=getchar();
}
return ans*f;
}
void rmq_init(){
for(int i=0;i<n;i++) d[i][0]=read();
for(int j=1;j<=21;j++)
for(int i=0;i+(1<<j)-1<n;i++)
d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
int rmq(int l,int r){
int k=log2(r-l+1);
return max(d[l][k],d[r-(1<<k)+1][k]);
}
int main(){
n=read();
m=read();
rmq_init();
int x,y;
for(int i=0;i<m;i++){
x=read();
y=read();
x--;
y--;
printf("%d\n",rmq(x,y));
}
return 0;
}
值得注意的是，這裡要用快讀，否則就會這樣：
然而當時自己改了半天代碼，直到沒辦法看了題解才知道要用快讀。
然而更尴尬的是，用了快讀之後：
為什麼呢？因為我是用cout流輸出答案的，改為printf之後就全對了：
三、總結
對時間要求高的題目，在求解時，讀入用快讀，輸出用printf而不是cout
四、作者
Bowen