題解 區間中最大的數

2022-11-24 17:26:14 字數 1474 閱讀 2076

給出一個有n個數的序列,編號0 - n - 1。進行q次查詢,查詢編號i至j的所有數中,最大的數是多少。

例如: 1 7 6 3 1。i = 1, j = 3,對應的數為7 6 3,最大的數為7。(該問題也被稱為rmq問題)

input

第1行:1個數n,表示序列的長度。(2 <= n <= 10000) 第2 - n + 1行:每行1個數,對應序列中的元素。(0 <= si <= 10^9) 第n + 2行:1個數q,表示查詢的數量。(2 <= q <= 10000) 第n + 3 - n + q + 2行:每行2個數,對應查詢的起始編號i和結束編號j。(0 <= i <= j <= n - 1)

output

共q行,對應每一個查詢區間的最大值。

sample input51

7631

30 1

1 33 4

sample output77

3這道題很顯然,是一道rmq問題,因為題目已經宣告瞭……

這就是一個很模板類的題目,但是小編仍然錯了好多次,那麼就講一講rmq具體怎麼理解吧。

對於rmq問題來說一般對於空間和時間都有一定要求,空間上開不起10000*10000的二維陣列,時間上也總會超時。

#includeusing namespace std;

int n,num[10000],q,x,y;

int head=0,tail=0;

int rmq[5000][5000];

int main()

scanf("%d",&q);

for(int i=1;i<=q;i++)

return 0;

}

這是小編最開始暴力求解的**,時間複雜度為o(n^2)。

為了節約時間不得不採用o(n log n)的做法,那就是採用分治的思想。

設陣列rmq[i][j]表示從i開始(包括i)後面2^j個數中的最大值,這樣遞推的關係式就變成了:

#includeusing namespace std;

unsigned long long n,num[10000],q,l,r;

unsigned logg[10000],rmq[10000][50];

int main()

for(int j=1;j<=18;j++)

for(int i=0;i+(1<>q;

for(int i=1;i<=q;i++)

{ cin>>l>>r;

int k=logg[r-l+1];

cout

pow貌似不能放進陣列的中,會報錯,所以小編這裡替換成了位運算

logg其實是因為已經有函式log了,當然直接用log函式應該也可以,記得要上取整,但是不知道為什麼就re了,還是手寫吧……

1062 序列中最大的數

1062 序列中最大的數 基準時間限制 1 秒 空間限制 131072 kb 分值 10 難度 2級演算法題 收藏關注有這樣一個序列a a 0 0 a 1 1 a 2i a i a 2i 1 a i a i 1 輸入一個數n,求a 0 a n 中最大的數。a 0 0,a 1 1,a 2 1,a 3 ...

找字串中最大的迴文

原帖 背景 所謂對稱子字串,就是這個子字串要麼是以其中一個詞對稱 比如 aba abcba 要麼就完全對稱 比如 abba abccba 問題 給你一個字串,找出該字串中對稱的子字串的最大長度。思路 首先,我們用字元陣列 char array 來保持這個字串,假設現在已經遍歷到第 i 個字元,要找出...

陣列中最大的子陣列之和

一個有n個整數元素的一維陣列 a 0 a 1 a n 1 求子陣列之和的最大值。例子 1,2,3,5,3,2 返回 8 0,2,3,5,1,2 返回 9 9,2,3,5,3 返回 2 思路 從頭遍歷陣列元素,並累加求和,如果和小於0就自當前元素從新開始,否則就一直累加,取其中最大值便為解。方法1 蠻...