Problem

很多學(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

---

Hint

Huge input,the C function scanf() will work better than cin

---

題解：線段樹裸題。注意一下Hint，要用long long和讀入的處理。

#include <iostream> #include <bits/stdc++.h> using namespace std; const int MAX = 200000; struct node {int l, r;int w; }; struct node tree[MAX *4 + 1]; int ans = 0; void BuildTree(int l, int r, int k) {tree[k].l = l;tree[k].r = r;if(l == r){scanf("%d",&tree[k].w);return ;}int m = (tree[k].l + tree[k].r) >> 1;BuildTree(l, m,k << 1);BuildTree(m + 1, r, k << 1 | 1);tree[k].w = max(tree[k << 1].w, tree[k << 1 | 1].w); } void SingleModify(int k, int x, int y) {if(tree[k].l == tree[k].r){tree[k].w = y;return ;}int m = (tree[k].l + tree[k].r) / 2;if(x <= m) SingleModify(k<<1,x,y);else SingleModify(k<<1|1,x,y);tree[k].w = max(tree[k<<1].w, tree[k<<1|1].w); } void IntervalQuery(int k, int x, int y) {if(tree[k].l >= x && tree[k].r <= y){ans = max(ans,tree[k].w);return ;}int m = (tree[k].l + tree[k].r) >>1;if(x <= m) IntervalQuery(k<<1,x,y);if(y > m) IntervalQuery(k <<1 |1,x, y); } char op; int main() {int n, m,x,y;while(~scanf("%d %d", &n, &m)){BuildTree(1,n,1);while(m --){getchar();scanf("%c %d %d",&op, &x, &y);if(op == 'Q'){ans = 0;IntervalQuery(1,x,y);printf("%d\n",ans);}else if(op =='U'){SingleModify(1,x,y);}}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lcchy/p/10139632.html

總結(jié)

以上是生活随笔為你收集整理的I Hate It （HDU 1754）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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