原題：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;
}
