本文共 1352 字，大约阅读时间需要 4 分钟。
#include #include #include #include #include #include #include #include #include #include #include #define M 200000#define inf 0x3f3f3f3ftypedef long long ll;using namespace std;struct Data{ int max; int left, right;}tree[M*4];int n, m;int ans;int x, y;char ch;void built(int l,int r,int k) { tree[k].left = l, tree[k].right = r; if (l == r) { scanf("%d", &tree[k].max); return; } int mid = (l + r) / 2; built(l, mid,k*2); built(mid + 1, r, k * 2 + 1); tree[k].max = max(tree[k * 2].max, tree[k * 2 + 1].max);}void search(int k) { if (tree[k].left >= x && tree[k].right <= y) { ans = max(ans, tree[k].max); return; } int mid = (tree[k].left + tree[k].right) / 2; if (x <= mid) search(k * 2); if(y>mid) search(k * 2 + 1);}void change_inv(int k) { if (tree[k].left == tree[k].right) { tree[k].max = y; return; } int mid = (tree[k].left + tree[k].right) / 2; if (x <= mid) change_inv(k * 2); else change_inv(k * 2 + 1); tree[k].max = max(tree[k * 2].max, tree[k * 2 + 1].max);}int main() { while (scanf("%d%d",&n,&m)!=EOF){ built(1, n, 1); while (m--){ cin >> ch; scanf("%d%d", &x, &y); if(ch=='Q'){ ans = 0; search(1); printf("%d\n", ans); } else { change_inv(1); } } } return 0;}
转载于:https://www.cnblogs.com/caibingxu/p/10777073.html