題目描述

老管家是一個聰明能干的人。他為財主工作了整整10年，財主為了讓自已賬目更加清楚。要求管家每天記k次賬，由于管家聰明能干，因而管家總是讓財主十分滿意。但是由于一些人的挑撥，財主還是對管家產生了懷疑。于是他決定用一種特別的方法來判斷管家的忠誠，他把每次的賬目按1，2，3…編號，然后不定時的問管家問題，問題是這樣的：在a到b號賬中最少的一筆是多少？為了讓管家沒時間作假他總是一次問多個問題。

輸入格式

輸入中第一行有兩個數m,n表示有m(m<=100000)筆賬,n表示有n個問題，n<=100000。

第二行為m個數,分別是賬目的錢數

后面n行分別是n個問題,每行有2個數字說明開始結束的賬目編號。

輸出格式

輸出文件中為每個問題的答案。具體查看樣例。

輸入輸出樣例

輸入 #1

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

輸出 #1

2 3 1

裸的ST模板題，中文題不寫題意。

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> using namespace std; int map[1000005][20]; int N,K; void work() {int i,j;for(j=1;1<<j<=N;j++)for(i=1;i+(1<<j)-1<=N;i++)//i+(1<<j)-1<=n是為了保證區間左端點不超出總數nmap[i][j]=min(map[i][j-1],map[i+(1<<j-1)][j-1]);//實質是動態規劃 } int question(int z,int y) {int x=int (log(y-z+1)/log(2));//注意y-z要加一才為區間長度return min(map[z][x],map[y-(1<<x)+1][x]);//分別以左右兩個端點為基礎，向區間內跳1<<x的最 //大值; } int main() {scanf("%d",&N);//輸入數據總數scanf("%d",&K);//輸入詢問次數kfor(int i=1;i<=N;i++)scanf("%d",&map[i][0]);//數據輸入加初始化，即從i開始向右走2的0次方的區間中的最大值，（注//意i到i的長度為一）。work();//預處理for(int i=1;i<=K;i++){int a,b;scanf("%d%d",&a,&b);printf("%d ",question(a,b));//輸出結果}return 0; }

?

總結

以上是生活随笔為你收集整理的洛谷 P1816 忠诚 ST函数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。