首页 > 代码库 > I Hate It(HDU1754)

I Hate It(HDU1754)

2024-07-15 14:57:01   220人阅读

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

题目大意。。。。。。如红色部分。。。。

解题思路。。。。线段树的应用。。调用线段树模板，每个根节点储存它们子节点的最大值。每次遍历，只需要找到它们对应的位置，返回它们根节点储存的值即可。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1754

 

  1 #include<stdio.h>  2   3 #define max(x1, y1) ((x1) > (y1) ? (x1) : (y1))  4   5 struct node  6   7 {  8   9     int left , right , max; 10  11 } T[600010]; 12  13 int a[200005]; 14  15 void create (int u,int l,int r)      //第u个节点的最左端为l，最右端为r。 16  17 {                         18  19     T[u].left  = l; 20  21     T[u].right = r; 22  23     int mid = (l+r)/2; 24  25     if( l == r) 26  27     {  T[u].max = a[r];  return ; } 28  29     create(u+u ,l, mid ); 30  31     create(u+u + 1,mid + 1, r ); 32  33     T[u].max =max(T[u+u].max,T[u+u+1].max);  //根节点储存它们子节点的最大成绩 34  35 } 36  37 int search_max(int l ,int r,int i)      //查找区间[l，r]上的最大值，值函数里i应该写1 38  39 { 40  41     if(l <= T[i].left &&T[i].right<= r) 42  43         return T[i].max; 44  45     else 46  47     { 48  49         int ans1 = -9999999, ans2 =-9999999; 50  51         if(l <= T[i+i].right)    ans1 = search_max(l,r,i+i); 52  53         if(r >= T[i+i+1].left)   ans2 = search_max(l,r,i+i+1); 54  55         return max(ans1,ans2);  56  57     } 58  59 } 60  61 void change_tree(int order , int num,int i) //改变输入的数据中序号为order的值为num，同时更新该树 62  63 { 64  65     if(T[i].left == T[i].right) 66  67     { 68  69         T[i].max = num; 70  71         return ; 72  73     } 74  75     else 76  77     { 78  79         if( order <= T[i+i].right)     change_tree(order,num,i+i); 80  81         else                      change_tree(order,num,i+i+1); 82  83         T[i].max = max(T[i+i].max,T[i+i+1].max); 84  85     } 86  87 } 88  89 int main () 90  91 { 92  93     int n,m,A,B; 94  95     char c; 96  97     int i; 98  99    while(scanf("%d%d",&n,&m)!=EOF)100 101     {102 103         for(i=1;i<=n;i++)104 105            scanf("%d",&a[i]);106 107         create(1,1,n);108 109         for(i=1;i<=m;i++)110 111         {112 113             getchar();114 115             scanf("%c%d%d",&c,&A,&B);116 117             if(c==‘Q‘)118 119                printf("%d\n",search_max(A,B,1));120 121             else122 123             {124 125                 a[A] = B;126 127                 change_tree(A,B,1);128 129             }130 131         }132 133     }134 135     return 0 ;136 137 }
代码

 


联系
我们