RMQ



前言

RMQ是区间最值查询，多种算法可解，本文采用ST算法、线段树求解
原本使用了莫队算法求解，但还是TLE了，故删除那部分的代码

Balanced Lineup - POJ 3264

题意
询问给定区间中最大值和最小值的差值
思路
ST算法：

	#include <iostream>
	#include <cstdio>
	#include <algorithm>
	#include <cstring>
	#include <cmath>
	#include <stack>
	#include <queue>
	#include <map>
	using namespace std;
	typedef long long ll;
	const int N = 50005;
	const int M = 20;

	int arr_max[N][M];
	int arr_min[N][M];

	void RMQ(int n){
	    for(int j = 1; (1 << j) <= n; j++){
	        for(int i = 1; i + (1 << j) - 1 <= n; i++){
	            arr_max[i][j] = max(arr_max[i][j - 1], arr_max[i + (1 << (j - 1))][j - 1]);
	            arr_min[i][j] = min(arr_min[i][j - 1], arr_min[i + (1 << (j - 1))][j - 1]);
	        }
	    }
	}

	int query(int l, int r, int p){
	    int k = log(r - l + 1)/log(2);
	    if(p == 0)  return max(arr_max[l][k], arr_max[r - (1 << k) + 1][k]);
	    else        return min(arr_min[l][k], arr_min[r - (1 << k) + 1][k]);
	}

	int main(){
	    int n, m;
	    while(~scanf("%d%d", &n, &m)){
	        for(int i = 1; i <= n; i++){
	            scanf("%d", &arr_max[i][0]);
	            arr_min[i][0] = arr_max[i][0];
	        }
	        RMQ(n);

	        while(m--){
	            int p, q;
	            scanf("%d%d", &p, &q);
	            printf("%d\n", query(p, q, 0) - query(p, q, 1));
	        }
	    }
	}


线段树：

	#include <cstdio>
	#include <iostream>
	#include <cstring>
	#include <cstdlib>
	#include <ctime>
	#define lson l, m, rt << 1
	#define rson m + 1, r, rt << 1 | 1
	using namespace std;
	const int N = 200000 + 15;
	const int inf = 0x3f3f3f3f;

	int sum[N << 2][2];
	int a[N];

	void pushUp(int rt){
	    sum[rt][0] = max(sum[rt << 1][0], sum[rt << 1 | 1][0]);
	    sum[rt][1] = min(sum[rt << 1][1], sum[rt << 1 | 1][1]);
	}

	void build(int l, int r, int rt){
	    if(l == r){
	        sum[rt][0] = sum[rt][1] = a[l];
	        return;
	    }
	    int m = (l + r) >> 1;
	    build(lson);
	    build(rson);
	    pushUp(rt);
	}

	int query(int ql, int qr, int p, int l, int r, int rt){
	    if(ql <= l && r <= qr){
	        return sum[rt][p];
	    }
	    int ans = (p == 0 ? 0 : inf);
	    int m = (l + r) >> 1;
	    if(ql <= m)     ans = query(ql, qr, p, lson);
	    if(m <  qr){
	        if(p == 0)  ans = max(ans, query(ql, qr, p, rson));
	        else        ans = min(ans, query(ql, qr, p, rson));
	    }
	    return ans;
	}

	int main(){
	    int n, q;
	    while(~scanf("%d%d", &n, &q)){
	        for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); }
	        build(1, n, 1);

	        while(q--){
	            int l, r;
	            scanf("%d%d", &l, &r);
	            printf("%d\n", query(l, r, 0, 1, n, 1) - query(l, r, 1, 1, n, 1));
	        }
	    }
	}