NKLINEUP - Xếp hàng
Tác giả: ladpro98
Ngôn ngữ: C++
//http://vn.spoj.com/problems/NKLINEUP/
#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define mid (l + r >> 1)
#define left k + k
#define right left + 1
const int N = 50005;
const int oo = 1000000000;
using namespace std;
int n, q;
struct segment_tree {
ii it[4 * N]; int n;
segment_tree(int nn) {n = nn;}
void Upd(int k, int l, int r, int i, int v) {
if (l > r || i < l || r < i) return;
if (l == r) {it[k].X = it[k].Y = v; return;}
Upd(left, l, mid, i, v); Upd(right, mid + 1, r, i, v);
it[k].X = max(it[left].X, it[right].X);
it[k].Y = min(it[left].Y, it[right].Y);
}
ii Get(int k, int l, int r, int i, int j) {
if (l > r || r < i || j < l) return ii(0, oo);
if (i <= l && r <= j) return it[k];
ii ll = Get(left, l, mid, i, j), rr = Get(right, mid + 1, r, i, j);
return ii(max(ll.X, rr.X), min(ll.Y, rr.Y));
}
void Upd(int i, int v) {Upd(1, 1, n, i, v);}
ii Get(int i, int j) {return Get(1, 1, n, i, j);}
};
int main()
{
scanf("%d %d", &n, &q);
int i, x, l, r; ii res;
segment_tree IT (n);
for(int i = 1; i <= n; i++) {scanf("%d", &x); IT.Upd(i, x);}
while (q--) {
scanf("%d %d", &l, &r);
res = IT.Get(l, r);
printf("%d\n", res.X - res.Y);
}
return 0;
}