[TIOJ 1603] 胖胖殺蚯事件

原題：http://tioj.ck.tp.edu.tw/problems/1603
AC：http://tioj.ck.tp.edu.tw/submissions/17785

解題方向：RMQ


題目大意：區間最大值減最小值

解法：RMQ裸題，沒有修改，所以想要線段樹、Treap、莫對、塊狀練表等等做一做就會AC了，可以拿來實驗很多新方法的題目XD。這裡使用的是Sparse Table，因為沒有修改，顯得特別有優勢。

看到學弟最近在寫這題，無聊來刷了一下Rank~

列舉各方法複雜度

方法	建構資料	查詢	備註
Sparse Table	$n\log n$	$1$	黑魔法加持
線段樹	$n\log n$	$\log n$
樹堆	$n\log n$	$\log n$	常數大
莫對數組	$n\log n+n\sqrt{n}$	$1$
塊狀鍊表	$n\sqrt{n}$	$\sqrt{n}$

學高級技巧時，也別忘了最單純的想法

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll spM[17][100001];
ll spm[17][100001];
int main()
{
    #ifdef DBG
    //freopen("case.in", "r" , stdin);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N,Q,gap,jmp;
    cin>>N>>Q;
    for(int i=1;i<=N;++i)
    {
        cin>>spM[0][i];
        spm[0][i]=spM[0][i];
    }
    for(int i=1; (1<<i)<=N; ++i )
    {
        jmp = ( 1<<(i-1) );
        for(int j=1; j+jmp<=N; ++j )
        {
            spM[i][j] = max( spM[i-1][j] , spM[i-1][j+jmp] ); 
            spm[i][j] = min( spm[i-1][j] , spm[i-1][j+jmp] );
        }
    }
    while(Q--)
    {
        int L,R;
        cin>>L>>R;
        gap = 31 - __builtin_clz(abs(L-R)+1);
        cout<< max( spM[gap][L],spM[gap][R-(1<<gap)+1] )
              -min( spm[gap][L],spm[gap][R-(1<<gap)+1] ) << '\n';
    }
}

同場加映線段樹

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
pii data[400000];
pii merge(const pii &a,const pii &b)
{
    return { min(a.first,b.first) , max(a.second,b.second) };
}

void update(int i,ll v,int L,int R,int I)
{
    if(L==R){
        data[I]={v,v};
        return ;
    }
    int M = (L+R)/2;
    if(i<=M)update(i,v,L,M,I*2+1);
    else update(i,v,M+1,R,I*2+2);
    data[I] = merge(data[I*2+1],data[I*2+2]);
}

pii find(int l,int r,int L,int R,int I)
{
    if( L==l && R==r ) return data[I];
    int M = (L+R)/2;
    if ( r<=M ) return find(l,r,L  ,M,I*2+1);
    if ( M< l ) return find(l,r,M+1,R,I*2+2);
    return merge(   find(l  ,M,L  ,M,I*2+1),
                    find(M+1,r,M+1,R,I*2+2));
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N,M,a,b;
    ll t;
    cin>>N>>M;
    for(int i=1;i<=N;++i)
    {
        cin>>t;
        update(i,t,1,N,0);
    }
    while(M--)
    {
        cin>>a>>b;
        auto p = find(a,b,1,N,0);
        cout<<p.second-p.first<<'\n';
    }
    return 0;
}