P2880 Balanced Lineup G

求区间的最大值与最小值之差。

Solution

ST 表/线段树/RMQ

线段树做法：

#define lc u<<1
#define rc u<<1|1
int a[50010];
struct Tree { //线段树
    ll l, r, max, min;
}tr[200010];
void pushup(ll u) { //上传
    tr[u].max = max(tr[lc].max, tr[rc].max);
    tr[u].min = min(tr[lc].min, tr[rc].min);
}
void build(ll u, ll l, ll r) { //建树
    tr[u] = {l,r,a[l],a[l]};
    if (l == r) return;
    ll m = l + r >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(u);
}
ll querymin(ll u, ll l, ll r) { //区查
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].min;
    ll m = tr[u].l + tr[u].r >> 1;
    ll ans = INTMAX_MAX;
    if (l <= m) ans = min(ans, querymin(lc, l, r));
    if (r > m) ans = min(ans, querymin(rc, l, r));
    return ans;
}
ll querymax(ll u, ll l, ll r) { //区查
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].max;
    ll m = tr[u].l + tr[u].r >> 1;
    ll ans = -1e18;
    if (l <= m) ans = max(ans, querymax(lc, l, r));
    if (r > m) ans = max(ans, querymax(rc, l, r));
    return ans;
}
void solve() {
    int n, q;cin >> n >> q;
    for (int i = 1;i <= n;i++)cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int l, r;cin >> l >> r;
        cout << querymax(1, l, r) - querymin(1, l, r) << '\n';
    }
}