[TIOJ] 1995. 桑京邀請賽

題目連結:http://tioj.infor.org/problems/1995

---

噁爛的壓常數題，吳勝福居然原本官方解答是自己手寫3bytes整數，有夠可怕，好加在鄭天鈞夠聰明，讓我們免於這種可怕的地獄。
他的做法是建立一個Sparse Table，然而我們會發現我們正常sparse table會用掉$O(n log n)$記憶體的原因是因為我們要可以應付在線詢問，然而像這題離線的其實可以用$O(n)$的記憶體就好了，而少掉那$logn$也可簡單，就是你每次用完一條就丟掉，因為建立某一條的時候就可以把符合那條區間的詢問全部算好。此外我這裡因為沒把詢問排序好是因為若排序好就要多一條的記憶體來記錄原本誰是誰，所以只好讓詢問退化成$logN$，每建好一條就把所有詢問檢查過一遍。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2500000 + 1;
const int M = 1000000 + 1;

int L[M], R[M], arr[N];

int main(){
	int n, m; scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&L[i],&R[i]);
		L[i]--; R[i]--;
	}
	for(int i=0;i<n;i++) scanf("%d",&arr[i]);
	for(int j=0;(1<<j)<=n;j++){
		for(int q=0;q<m;q++){
			if(R[q]==-1) continue;
			int logN = 31-__builtin_clz(R[q]-L[q]+1);
			if(j!=logN) continue;
			L[q] = max(arr[L[q]], arr[R[q]-(1<<logN)+1]);
			R[q] = -1;
		}
		for(int i=0;i+(1<<(j+1)) <= n;i++){
			arr[i] = max(arr[i], arr[i+(1<<j)]);
		}
	}
	for(int i=0;i<m;i++) printf("%d\n", L[i]);
	return 0;
}