POJ 3264 Balanced Lineup

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500001, INF = 0x3f3f3f3f;
int n, m, w[N], l, r, t1[N], t2[N];
int lowbit(int x) {
    return x & -x;
}
void update(int i) {
    for (; i <= n; i += lowbit(i)) {
        t1[i] = t2[i] = w[i];
        int li = lowbit(i);
        for (int j = 1; j < li; j <<= 1)
            t1[i] = min(t1[i], t1[i - j]), t2[i] = max(t2[i], t2[i - j]);
    }
}
int find_max(int l, int r) {
    int ans = 0;
    while (r >= l) {
        ans = max(ans, w[r]);
        for (--r; r - lowbit(r) > l; r -= lowbit(r))
            ans = max(ans, t2[r]);
    }
    return ans;
}
int find_min(int l, int r) {
    int ans = INF;
    while (r >= l) {
        ans = min(ans, w[r]);
        for (--r; r - lowbit(r) > l; r -= lowbit(r))
            ans = min(ans, t1[r]);
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    memset(t1, 0x3f, sizeof(t1));
    memset(t2, -0x3f, sizeof(t2));
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &w[i]);
        update(i);
    }
    while (m--) {
        scanf("%d%d", &l, &r);
        printf("%d\n", find_max(l, r) - find_min(l, r));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, h, l, r;
const int N = 500001, INF = 0x3f3f3f3f;
struct Node {
    int l, r, min_val, max_val;
} tr[N << 2];
void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0};
    if (l == r) {
        scanf("%d", &h), tr[u].min_val = tr[u].max_val = h;
    } else {
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        tr[u].min_val = min(tr[u << 1].min_val, tr[u << 1 | 1].min_val);
        tr[u].max_val = max(tr[u << 1].max_val, tr[u << 1 | 1].max_val);
    }
}
int find_max(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].max_val;
    int mid = (tr[u].l + tr[u].r) >> 1, ans = -INF;
    if (l <= mid) ans = find_max(u << 1, l, r);
    if (r > mid) ans = max(ans, find_max(u << 1 | 1, l, r));
    return ans;
}
int find_min(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].min_val;
    int mid = (tr[u].l + tr[u].r) >> 1, ans = INF;
    if (l <= mid) ans = find_min(u << 1, l, r);
    if (r > mid) ans = min(ans, find_min(u << 1 | 1, l, r));
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while (m--) {
        scanf("%d%d", &l, &r);
        printf("%d\n", find_max(1, l, r) - find_min(1, l, r));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 500001, M = 19;
int n, m, l, r, h[N], f1[N][M], f2[N][M];
void init() {
    for (int j = 0; j < M; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            if (!j) f1[i][j] = f2[i][j] = h[i];
            else
                f1[i][j] = min(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]),
                f2[i][j] = max(f2[i][j - 1], f2[i + (1 << (j - 1))][j - 1]);
}
int find_max(int l, int r) {
    int len = r - l + 1, k = log(len) / log(2);
    return max(f2[l][k], f2[r - (1 << k) + 1][k]);
}
int find_min(int l, int r) {
    int len = r - l + 1, k = log(len) / log(2);
    return min(f1[l][k], f1[r - (1 << k) + 1][k]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
    init();
    while (m--) {
        scanf("%d%d", &l, &r);
        printf("%d\n", find_max(l, r) - find_min(l, r));
    }
    return 0;
}