首页 > 代码库 > HDU 1754 I Hate It(线段树)

HDU 1754 I Hate It(线段树)

2024-07-16 00:33:48   221人阅读

B - I Hate It
Time Limit:3000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status

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 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5
 

Sample Output

5659

Hint

Huge input,the C function scanf() will work better than cin
 
这道题和HDU1166敌兵布阵差不多
同样也是线段树入门题，学习如何创建线段树，更行线段树，查询线段树
 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 #include<stdlib.h> 6 #include<algorithm> 7 using namespace std; 8 struct node 9 {10     int l,r;11     int num;12     int mid()13     {14         return (l+r)/2;15     }16 }a[1000000];17 int maxn;18 19 void btree(int l,int r,int step)20 {21     a[step].l=l;22     a[step].r=r;23     if(l==r)24     {25         scanf("%d",&a[step].num);26         return ;27     }28     int mid=a[step].mid();29     btree(l,mid,step*2);30     btree(mid+1,r,step*2+1);31     a[step].num=max(a[step*2].num,a[step*2+1].num);32 }33 34 void ptree(int step,int vis,int val)35 {36     if(a[step].l==a[step].r&&a[step].l==vis)37     {38         a[step].num=val;39         return ;40     }41     int mid=a[step].mid();42     if(vis>mid) ptree(step*2+1,vis,val);43     else ptree(step*2,vis,val);44     a[step].num=max(a[step*2].num,a[step*2+1].num);45 }46 47 void maxtree(int l,int r,int step,int L,int R)48 {49     if(L<=l&&r<=R)50     {51         maxn=max(maxn,a[step].num);52         return ;53     }54     int mid=a[step].mid();55     if(L>mid)56         maxtree(mid+1,r,step*2+1,L,R);57     else if(R<=mid)58         maxtree(l,mid,step*2,L,R);59     else60     {61         maxtree(l,mid,step*2,L,R);62         maxtree(mid+1,r,step*2+1,L,R);63     }64 }65 66 int main()67 {68     int n,ope;69     while(scanf("%d %d",&n,&ope)!=EOF)70     {71         btree(1,n,1);72         while(ope--)73         {74             getchar();75             char ch;76             int x,y;77             scanf("%c %d %d",&ch,&x,&y);78             if(ch==‘Q‘)79             {80                 maxn=-1;81                 maxtree(1,n,1,x,y);82                 printf("%d\n",maxn);83             }84             if(ch==‘U‘)85                 ptree(1,x,y);86         }87     }88  89     return 0;90 }
View Code

 


联系
我们