基础线段树
View Code //poj3264#include#include #include using namespace std;const int maxn = 50002;struct cnode{ int l, r, nmin, nmax; cnode *pleft, *pright;};int ncount, cow[maxn], n, q, ansmax, ansmin;cnode tree[maxn * 2];void init(){ scanf("%d%d",&n,&q); ncount = 0;}void buildtree(cnode *pnow, int start, int end){ int mid; pnow -> l = start; pnow -> r = end; pnow -> nmin = 1000001; pnow -> nmax = -1; mid = (start + end) / 2; if (start != end) { ncount++; pnow -> pleft = tree + ncount; ncount++; pnow -> pright = tree + ncount; buildtree(pnow -> pleft, start, mid); buildtree(pnow -> pright, mid + 1, end); }}void insert(cnode *proot, int i, int v){ int mid; if (proot -> l == i && proot -> r == i) { proot -> nmin = v; proot -> nmax = v; return; } proot -> nmin = _cpp_min(v, proot -> nmin); proot -> nmax = _cpp_max(v, proot -> nmax); mid = (proot -> l + proot -> r) / 2; if (i <= mid) insert(proot -> pleft, i, v); else insert(proot -> pright, i, v);}void query(cnode *proot, int start, int end){ int mid;// if (proot -> nmin >= ansmin && proot -> nmax <= ansmax)// return; if (proot -> l == start && proot -> r == end) { ansmin = _cpp_min(proot -> nmin, ansmin); ansmax = _cpp_max(proot -> nmax, ansmax); return; } mid = (proot -> l + proot -> r) / 2; if (end <= mid) query(proot -> pleft, start, end); else if (start > mid) query(proot -> pright, start, end); else { query(proot -> pleft, start, mid); query(proot -> pright, mid + 1, end); }}int main(){ int i, t, u; //freopen("t.txt", "r", stdin); init(); buildtree(tree, 0, n - 1); for (i = 0; i < n; i++) { scanf("%d", &t); insert(tree, i, t); } for (i = 0; i < q; i++) { ansmin = 1000001; ansmax = -1; scanf("%d%d", &t, &u); query(tree, t - 1, u - 1); cout << ansmax - ansmin << endl; } return 0;}