很多學(xué)校流行一種比較的習(xí)慣。老師們很喜歡詢問(wèn)，從某某到某某當(dāng)中，分?jǐn)?shù)最高的是多少。?
這讓很多學(xué)生很反感。?

不管你喜不喜歡，現(xiàn)在需要你做的是，就是按照老師的要求，寫一個(gè)程序，模擬老師的詢問(wèn)。當(dāng)然，老師有時(shí)候需要更新某位同學(xué)的成績(jī)。

Input

本題目包含多組測(cè)試，請(qǐng)?zhí)幚淼轿募Y(jié)束。?
在每個(gè)測(cè)試的第一行，有兩個(gè)正整數(shù) N 和 M ( 0<N<=200000,0<M<5000 )，分別代表學(xué)生的數(shù)目和操作的數(shù)目。?
學(xué)生ID編號(hào)分別從1編到N。?
第二行包含N個(gè)整數(shù)，代表這N個(gè)學(xué)生的初始成績(jī)，其中第i個(gè)數(shù)代表ID為i的學(xué)生的成績(jī)。?
接下來(lái)有M行。每一行有一個(gè)字符 C (只取'Q'或'U') ，和兩個(gè)正整數(shù)A，B。?
當(dāng)C為'Q'的時(shí)候，表示這是一條詢問(wèn)操作，它詢問(wèn)ID從A到B(包括A,B)的學(xué)生當(dāng)中，成績(jī)最高的是多少。?
當(dāng)C為'U'的時(shí)候，表示這是一條更新操作，要求把ID為A的學(xué)生的成績(jī)更改為B。?

Output

對(duì)于每一次詢問(wèn)操作，在一行里面輸出最高成績(jī)。

Sample Input

5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5

Sample Output

5 6 5 9

問(wèn)題鏈接：https://cn.vjudge.net/contest/283761#problem/H

AC代碼：

#include<iostream> #include<cstring> #include<algorithm> #include<stdio.h> using namespace std; struct Tree {Tree() { memset(this, 0, sizeof(this)); }int left, right,sum,maxn,score; }; Tree tree[800020]; int pre[200005]; void update(int t) {tree[t].maxn = max(tree[t * 2].maxn, tree[t * 2 + 1].maxn);tree[t].sum = tree[t * 2].sum + tree[t * 2 + 1].sum; } void build_tree(int t,int left,int right) {tree[t].left = left;tree[t].right = right;if (left == right){tree[t].sum = pre[left];tree[t].maxn = pre[left];return;}int mid = (left + right) / 2;build_tree(t * 2, left, mid);build_tree(t * 2 + 1, mid + 1, right);update(t); } int inquiry_max(int t, int lef, int rig) {if (lef == tree[t].left&&rig == tree[t].right){return tree[t].maxn;}int mid = (tree[t].left+tree[t].right) / 2;if (rig <= mid)return inquiry_max(t * 2, lef, rig);else if (mid < lef)return inquiry_max(t * 2 + 1, lef, rig);else return max(inquiry_max(t * 2, lef, mid), inquiry_max(t * 2 + 1, mid+1, rig)); } void change(int t, int target, int figure) {if (tree[t].left == target && tree[t].right == target){tree[t].score = figure;tree[t].maxn = figure;return;}int mid = (tree[t].left + tree[t].right) / 2;if (target <= mid)change(t * 2, target, figure);else change(t * 2 + 1, target, figure);update(t); } int main() {int n, m;while (cin >> n >> m){for (int i = 1; i <= n; i++)scanf("%d", &pre[i]);build_tree(1, 1, n);int a=0, b=0;char c=0;while (m--){scanf("%s%d%d", &c, &a, &b);switch (c){case 'Q': printf("%d\n", inquiry_max(1, a, b)); break;case 'U':change(1, a, b); break;}} } }

?

總結(jié)

以上是生活随笔為你收集整理的二叉树：HDU1754的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。