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;
}

Download