AcWing 4340. 我讨厌它

Posted on Edited on In

原题为 HDU 1754 I Hate It。

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 <cstring>
#include <algorithm>
using namespace std;
const int N = 200001;
int n, m, a, b, w[N], tr[N];
char op[2];
int lowbit(int x) {
    return x & -x;
}
void update(int i) {
    for (; i <= n; i += lowbit(i)) {
        tr[i] = w[i];
        int li = lowbit(i);
        for (int j = 1; j < li; j <<= 1)
            tr[i] = max(tr[i], tr[i - j]);
    }
}
int query(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, tr[r]);
    }
    return ans;
}
int main() {
    while (~scanf("%d%d", &n, &m)) {
        memset(tr, 0, sizeof(tr));
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &w[i]);
            update(i);
        }
        while (m--) {
            scanf("%s%d%d", op, &a, &b);
            if (*op == 'Q') printf("%d\n", query(a, b));
            else w[a] = b, update(a);
        } 
    }
    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
43
44
45
46
47
48
49
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 200001, INF = -0x3f3f3f3f;
int n, m, a, b;
char op[2];
struct Node {
    int l, r, max_val;
} tr[N << 2];
void pushup(int u) {
    tr[u].max_val = max(tr[u << 1].max_val, tr[u << 1 | 1].max_val);
}
void build(int u, int l, int r) {
    tr[u] = {l, r, 0};
    if (l == r) {
        scanf("%d", &a), tr[u].max_val = a;
    } else {
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
int query(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 = query(u << 1, l, r);
    if (r > mid) ans = max(ans, query(u << 1 | 1, l, r));
    return ans;
}
void update(int u, int x, int k) {
    if (tr[u].l == tr[u].r) tr[u].max_val = k;
    else {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid) update(u << 1, x, k);
        else update(u << 1 | 1, x, k);
        pushup(u);
    }
}
int main() {
    while (~scanf("%d%d", &n, &m)) {
        build(1, 1, n);
        while (m--) {
            scanf("%s%d%d", op, &a, &b);
            if (*op == 'Q') printf("%d\n", query(1, a, b));
            else update(1, a, b);
        } 
    }
    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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 200001, INF = -0x3f3f3f3f;
int n, _n, m, a, b;
char op[2];
vector<int> tr;
int query(int u, int l, int r, int L, int R) {
    if (R < l || L > r) return INF;
    if (L <= l && r <= R) return tr[u];
    int mid = (l + r) >> 1, ans = INF;
    if (l <= mid) ans = query(u << 1, l, mid, L, R);
    if (r > mid) ans = max(ans, query(u << 1 | 1, mid + 1, r, L, R));
    return ans;
}
void update(int x, int k) {
    int i = _n + x;
    tr[i] = k;
    while (i > 1) {
        i >>= 1;
        tr[i] = max(tr[i << 1], tr[i << 1 | 1]);
    }
}
int main() {
    while (~scanf("%d%d", &n, &m)) {
        _n = n;
        while (__builtin_popcount(_n) != 1) _n++;
        tr = vector<int>(2 * _n, INF);
        for (int i = 0; i < n; ++i) scanf("%d", &tr[_n + i]);
        for (int i = _n - 1; i >= 1; --i) tr[i] = max(tr[i << 1], tr[i << 1 | 1]);
        while (m--) {
            scanf("%s%d%d", op, &a, &b);
            if (*op == 'Q') printf("%d\n", query(1, 0, _n - 1, a - 1, b - 1));
            else update(a - 1, b);
        } 
    }
    return 0;
}