I Hate It

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 97602    Accepted Submission(s): 36849

Problem Description

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

Output

对于每一次询问操作，在一行里面输出最高成绩。

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

Author

linle

Source

2007省赛集训队练习赛（6）_linle专场

Recommend

lcy   |   We have carefully selected several similar problems for you:  1698 1542 1394 2795 1540 

Statistic | Submit | Discuss | Note

Home | Top

Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2018 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 5, Server time : 2018-07-27 11:40:57, Gzip enabled

Administration

解析：基础入门的线段树，套用模板，每一区间，更新最大值 ；

另一种解法：hdu1754-树状数组求最值

第一种写法：

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a))const int maxn=200000+10;struct node{int l,r,mxn; }tree[maxn<<2];int ans,a[maxn]; char str[10];void build(int l,int r,int m) {tree[m].l=l;tree[m].r=r;if(l==r){tree[m].mxn=a[l];return ;}int mid=(l+r)>>1;build(l,mid,m<<1);build(mid+1,r,m<<1|1);tree[m].mxn=max(tree[m<<1].mxn,tree[m<<1|1].mxn); }void update(int a,int val,int m) {if(tree[m].l==a&&tree[m].r==a){tree[m].mxn=val;return ;}int mid=(tree[m].l+tree[m].r)>>1;if(a<=mid){update(a,val,m<<1);}elseupdate(a,val,m<<1|1);tree[m].mxn=max(tree[m<<1].mxn,tree[m<<1|1].mxn); }void query_sum(int l,int r,int m) {if(tree[m].l==l&&tree[m].r==r){ans=max(tree[m].mxn,ans);return ;}int mid=(tree[m].l+tree[m].r)>>1;if(r<=mid)query_sum(l,r,m<<1);else if(l>=mid+1)query_sum(l,r,m<<1|1);else{query_sum(l,mid,m<<1);query_sum(mid+1,r,m<<1|1);} } int main() {int n,m;while(scanf("%d%d",&n,&m)==2){for(int i=1; i<=n; i++)scanf("%d",&a[i]);build(1,n,1);while(m--){ scanf("%s",str);if(str[0]=='U'){int x,y;scanf("%d%d",&x,&y);update(x,y,1);}if(str[0]=='Q'){int x,y;scanf("%d%d",&x,&y);ans=-9999999;query_sum(x,y,1);printf("%d\n",ans);}}}return 0; }

第二种写法：

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a))const int maxn=200000+10;struct node{int l,r,mxn; }tree[maxn<<2];int ans,a[maxn]; char str[10];void build(int l,int r,int m) {tree[m].l=l;tree[m].r=r;if(l==r){tree[m].mxn=a[l];return ;}int mid=(l+r)>>1;build(l,mid,m<<1);build(mid+1,r,m<<1|1);tree[m].mxn=max(tree[m<<1].mxn,tree[m<<1|1].mxn); }int update(int a,int val,int m) {if(a<tree[m].l||tree[m].r<a){return tree[m].mxn;}if(tree[m].l==a&&tree[m].r==a){return tree[m].mxn=val; }int x=update(a,val,m<<1);int b=update(a,val,m<<1|1);tree[m].mxn=max(x,b);return tree[m].mxn; }int query_sum(int l,int r,int m) {//printf("%d %d %d\n",l,r,m);if(r<tree[m].l||tree[m].r<l)return 0;if(l<=tree[m].l&&tree[m].r<=r){return tree[m].mxn;}int a=query_sum(l,r,m<<1);int b=query_sum(l,r,m<<1|1);return max(a,b); } int main() {int n,m;while(scanf("%d%d",&n,&m)==2){for(int i=1; i<=n; i++)scanf("%d",&a[i]);build(1,n,1);while(m--){scanf("%s",str);if(str[0]=='U'){int x,y;scanf("%d%d",&x,&y);update(x,y,1);}if(str[0]=='Q'){int x,y;scanf("%d%d",&x,&y);printf("%d\n",query_sum(x,y,1));}}}return 0; }

 

总结

以上是生活随笔为你收集整理的hdu1754（简单线段树）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。