python/TangDou/AcWing/BIT/HDU1754.cpp

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;
const int N = 200010;

int n, m;     // n个数，m个操作
int a[N];     // 原始数据
char op[110]; // 指令字符串

// 树状数组求最大值模板
int c[N];
int lowbit(int x) {
    return x & -x;
}
void update(int x, int d) {
    for (int i = x; i < N; i += lowbit(i)) c[i] = max(c[i], d);
}

int query(int x, int y) {
    int mx = 0;
    while (x <= y) {
        mx = max(mx, a[y]);
        for (--y; y - x >= lowbit(y); y -= lowbit(y)) mx = max(mx, c[y]);
    }
    return mx;
}

/*
答案：
5
6
5
9
*/
int main() {
#ifndef ONLINE_JUDGE
    freopen("HDU1754.in", "r", stdin);
#endif
    // n个数，m个操作
    while (~scanf("%d %d", &n, &m)) {
        memset(c, 0, sizeof c);        // 清空树状数组
        for (int i = 1; i <= n; i++) { // 读入n个数
            scanf("%d", &a[i]);
            update(i, a[i]); // i这个位置最大值是a[i],这里不是add,而是update
        }

        int x, y;
        while (m--) {
            scanf("%s %d %d", op, &x, &y);
            if (op[0] == 'U') { // 更新操作，要求把id为x的学生的成绩更改为y
                a[x] = y;       // ①将原数组修改
                update(x, y);   // ②将映射的树状数组修改,使得统计信息也相应修改完成
            } else
                printf("%d\n", query(x, y)); // 询问id从x到y(包括x,y)的学生当中，最大值是多少
        }
    }
    return 0;
}