题目链接:http://poj.org/problem?id=3264 裸裸的线段树,就是一个结点存储两个值,一个是区间内最大值,一个是区间内最小值,最后做个差了事儿~~这两天被很多题虐爆了,今天放松一下心情……
![](/Images/OutliningIndicators/ContractedBlock.gif) view code 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8 #define lson l, m, rt << 1 9 #define rson m + 1, r, rt << 1 | 1 10 const int maxn = 50010; 11 int MAX[maxn << 2], MIN[maxn << 2]; 12 void PushUp(int rt) 13 { 14 MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]); 15 MIN[rt] = min(MIN[rt << 1], MIN[rt << 1 | 1]); 16 } 17 void build(int l, int r, int rt) 18 { 19 if (l == r) 20 { 21 scanf("%d", &MAX[rt]); 22 MIN[rt] = MAX[rt]; 23 return; 24 } 25 int m = (l + r) >> 1; 26 build(lson); 27 build(rson); 28 PushUp(rt); 29 } 30 int queryzg(int ll, int rr, int l, int r, int rt) 31 { 32 if (ll <= l && rr >= r) return MAX[rt]; 33 int m = (l + r) >> 1; 34 int ret = 0; 35 if (ll <= m) ret = max(ret, queryzg(ll, rr, lson)); 36 if (rr > m) ret = max(ret, queryzg(ll,rr, rson)); 37 return ret; 38 } 39 int queryza(int ll, int rr, int l, int r, int rt) 40 { 41 if (ll <= l && rr >= r) return MIN[rt]; 42 int m = (l + r) >> 1; 43 int ret = 210000000; 44 if (ll <= m) ret = min(ret, queryza(ll, rr, lson)); 45 if (rr > m) ret = min(ret, queryza(ll, rr, rson)); 46 return ret; 47 } 48 int main() 49 { 50 int n, q; 51 while (scanf("%d%d", &n, &q) != EOF) 52 { 53 build(1, n, 1); 54 while (q--) 55 { 56 int x, y; 57 scanf("%d%d", &x, &y); 58 int da = queryzg(x, y, 1, n, 1); 59 int xi = queryza(x, y, 1, n, 1); 60 int ans = da - xi; 61 printf("%d\n", ans); 62 } 63 } 64 return 0; 65 } 66
|