[Usaco 2007 Jan]Balanced Lineupフライボード試合

タイトルの説明
毎日、農夫のジョンのN(1<=N<=50000)頭牛はいつも同じシーケンスで並んでいる.ある日、ジョンは牛たちに飛盤の試合をさせることにした.彼はペアの中で連続した牛を探して試合をするつもりだ.しかし、レベルの差を避けるために、牛の身長はあまり違わないはずだ.ジョンはQ(1<=Q<=180000)個の可能な牛の選択とすべての牛の身長(1<=身長<=1000000)を用意した.彼は各グループの中で最高と最低の牛の身長の違いを知りたいと思っている.注意:最大データでは、入力と出力が実行時間の大部分を占める.
入力フォーマット
1行目:NとQ.*2.N+1行目:i+1行目はi番目の学生の身長である.
N+2..N+Q+1行:2つの整数、AとB(1<=A<=B<=N)は、AからBまでのすべての学生を表す.
出力フォーマット
第1..Q行:すべての質問の答え(最高と最低の学生の身長差)、行ごとに1つ.
暴力的なやり方を考慮して,区間内の各値を列挙するたびに最大値と最小値を求めて減算すればよい.時間的複雑度はO(QN)であった.明らかに通れない.
実際,このRMQ問題は,stテーブルやセグメントツリーを直接打つことで解くことができ,時間的複雑さはすべてO(Qlogn)であるべきである.

#include
#include
#include
#define maxn 50001
using namespace std;
  
inline int read(){
    register int x(0),f(1); register char c(getchar());
    while(c>1;
    build(d<<1,l,mid),build(d<<1|1,mid+1,r);
    t[d].mmax=max(t[d<<1].mmax,t[d<<1|1].mmax);
    t[d].mini=min(t[d<<1].mini,t[d<<1|1].mini);
}
  
int getmax(int d,const int &l,const int &r){
    if(l<=t[d].l&&t[d].r<=r) return t[d].mmax;
    int mid=t[d].r+t[d].l>>1,ans=0x80808080;
    if(l<=mid) ans=max(ans,getmax(d<<1,l,r));
    if(mid>1,ans=0x3f3f3f3f;
    if(l<=mid) ans=min(ans,getmin(d<<1,l,r));
    if(mid

転載先:https://www.cnblogs.com/akura/p/10853425.html