题目链接：http://poj.org/problem?id=3264
写了一个更优美一点的
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 20 using namespace std; 21 22 #define fr first 23 #define sc second 24 #define pb(a) push_back(a) 25 #define Rint(a) scanf("%d", &a) 26 #define Rll(a) scanf("%I64d", &a) 27 #define Rs(a) scanf("%s", a) 28 #define FRead() freopen("in", "r", stdin) 29 #define FWrite() freopen("out", "w", stdout) 30 #define Rep(i, len) for(int i = 0; i < (len); i++) 31 #define For(i, a, len) for(int i = (a); i < (len); i++) 32 #define Cls(a) memset((a), 0, sizeof(a)) 33 #define Full(a) memset((a), 0x7f7f, sizeof(a)) 34 35 typedef struct Node { 36 int lo, hi; 37 Node() {} 38 Node(int l, int h) : lo(l), hi(h) {} 39 }Node; 40 41 #define lrt rt << 1 42 #define rrt rt << 1 | 1 43 const int maxn = 500010; 44 Node h[maxn<<1]; 45 int n, q; 46 47 void pushUP(int rt) { 48 h[rt].lo = min(h[lrt].lo, h[rrt].lo); 49 h[rt].hi = max(h[lrt].hi, h[rrt].hi); 50 } 51 52 void build(int l, int r, int rt) { 53 if(l == r) { 54 Rint(h[rt].lo); 55 h[rt].hi = h[rt].lo; 56 return; 57 } 58 int m = (l + r) >> 1; 59 build(l, m, lrt); 60 build(m+1, r, rrt); 61 pushUP(rt); 62 } 63 64 Node query(int L, int R, int l, int r, int rt) { 65 if(L <= l && r <= R) return h[rt]; 66 int m = (l + r) >> 1; 67 Node ret(0x7f7f7f, 0), tmp; 68 if(m >= L) { 69 tmp = query(L, R, l, m, lrt); 70 ret.lo = min(ret.lo, tmp.lo); 71 ret.hi = max(ret.hi, tmp.hi); 72 } 73 if(m < R) { 74 tmp = query(L, R, m+1, r, rrt); 75 ret.lo = min(ret.lo, tmp.lo); 76 ret.hi = max(ret.hi, tmp.hi); 77 } 78 return ret; 79 } 80 81 int main() { 82 // FRead(); 83 int a, b; 84 while(~Rint(n) && ~Rint(q)) { 85 build(1, n, 1); 86 while(q--) { 87 Rint(a); Rint(b); 88 Node ret = query(a, b, 1, n, 1); 89 printf("%d ", ret.hi - ret.lo); 90 } 91 } 92 return 0; 93 }