182. [USACO Jan07] 均衡隊形

★★?? 輸入文件：lineup.in?? 輸出文件：lineup.out???簡單對比
時間限制：4 s?? 內(nèi)存限制：128 MB

題目描述

農(nóng)夫約翰的 N (1 ≤ N ≤ 50,000) 頭奶牛，每天擠奶時總會按同樣的順序站好。一日，農(nóng)夫約翰決定為奶牛們舉行一個“終極飛盤”比賽。為簡化問題，他將從奶牛隊列中選出一個連續(xù)區(qū)間來進行游戲。不過，參加游戲的奶牛要玩的開心的話就不能在身高上差距太大。

農(nóng)夫約翰制定了 Q (1 ≤ Q ≤ 200,000) 個預(yù)定的參賽組，給出它們的身高 (1 ≤ 身高?≤ 1,000,000)。對每個參賽組，他需要你幫助確定組中最高牛和最低牛的身高差。

輸入格式

• 第 1 行: 兩個空格隔開的整數(shù)，N 和 Q。
• 第?2..N+1 行: 第 i+1 行包含一個整數(shù)表示第 i 頭牛的身高。
• 第?N+2..N+Q+1 行: 兩個整數(shù) A 和 B(1 ≤ A ≤ B ≤ N)，表示一個從 A 到 B 的參賽組區(qū)間。

輸出格式

• 第?1..Q 行: 每行包含一個整數(shù)來表示區(qū)間上最大身高差。

樣例輸入

6 3 1 7 3 4 2 5 1 5 4 6 2 2

樣例輸出

6 3 0

---

剛感覺是沒有修改的線段樹，掃一眼左欄有人說st表，感覺自己智障了....
// // main.cpp // cogs182 // // Created by Candy on 10/9/16. // Copyright ? 2016 Candy. All rights reserved. // #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; typedef long long ll; const int N=1e5+5,MOD=1e9+7; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x; } int n,q,a[N],l,r; int mx[N][20],mn[N][20]; void initRMQ(){for(int i=1;i<=n;i++) mx[i][0]=mn[i][0]=a[i];for(int j=1;j<=20;j++)for(int i=1;i+(1<<j)-1<=n;i++){mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);} } int qmx(int l,int r){int k=log(r-l+1)/log(2);return max(mx[l][k],mx[r-(1<<k)+1][k]); } int qmn(int l,int r){int k=log(r-l+1)/log(2);return min(mn[l][k],mn[r-(1<<k)+1][k]); } int main(int argc, const char * argv[]){freopen("lineup.in","r",stdin);freopen("lineup.out","w",stdout);n=read();q=read();for(int i=1;i<=n;i++) a[i]=read();initRMQ();for(int i=1;i<=q;i++){l=read();r=read();printf("%d\n",qmx(l,r)-qmn(l,r));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的COGS182 [USACO Jan07] 均衡队形[RMQ]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。