HDU1754 —— I Hate It 线段树单点修改及区间最大值-白红宇

HDU1754 —— I Hate It 线段树单点修改及区间最大值

阅读量：4701 次

发布时间：2019-06-09

本文共 2012 字，大约阅读时间需要 6 分钟。

题目链接：

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

这让很多学生很反感。

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

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

Hint

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

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 using namespace std;13 typedef long long LL;14 const double EPS = 1e-8;15 const int INF = 2e9;16 const LL LNF = 2e18;17 const int MAXN = 2e5+10;18 19 int maxv[MAXN*4];20 21 void push_up(int u)22 {23 maxv[u] = max(maxv[u*2], maxv[u*2+1]);24 }25 26 void add(int u, int l, int r, int pos, int val)27 {28 if(l==r)29 {30 maxv[u] = val;31 return;32 }33 34 int mid = (l+r)/2;35 if(pos<=mid) add(u*2, l, mid, pos, val);36 else add(u*2+1, mid+1, r, pos, val);37 push_up(u);38 }39 40 int query(int u, int l, int r, int x, int y)41 {42 if(x<=l && r<=y)43 return maxv[u];44 45 int ret = -INF;46 int mid = (l+r)/2;47 if(x<=mid) ret = max(ret, query(u*2, l, mid, x, y) );48 if(y>=mid+1) ret = max(ret, query(u*2+1, mid+1, r, x, y) );49 return ret;50 }51 52 int main()53 {54 int n, m;55 while(scanf("%d%d", &n, &m)!=EOF)56 {57 memset(maxv, 0, sizeof(maxv));58 char op[2]; int a, b;59 for(int i = 1; i<=n; i++)60 {61 scanf("%d", &a);62 add(1, 1, n, i, a);63 }64 65 for(int i = 1; i<=m; i++)66 {67 scanf("%s%d%d", op, &a, &b);68 if(op[0]=='U') add(1, 1, n, a, b);69 else printf("%d\n", query(1, 1, n, a, b));70 }71 }72 }