I hate it

时间：2022-01-07 04:58:19

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
题意：
给定N个按一定顺序排列的值，对这N个值进行两种操作：
1、查询某个区间[A,B]的最大值；
2、修改序号为A处的值；
 
线段树，更新节点，区间求最值
 
思路：这个题完全就是线段树的一个基础应用，就是建一个静态树，然后不根据输入区维护各个区间上的最值。用到了三个基本操作，建树，更新，查询。
 

代码如下：

#include "stdio.h"

#include <cstdio>

#include <climits>

using namespace std;

#define M ((L+R)>>1)

#define lson rt<<1,L,M

#define rson rt<<1|1,M+1,R

#define root 1,1,N

#define max(a,b) ((a>b)?a:b)

const int maxn = 200001;

int maxv[maxn << 2],ql,qr,tar,v,val[maxn];

inline void pushup(int rt)

 {

    maxv[rt] = max(maxv[rt<<1],maxv[rt<<1|1]);

}

void build(int rt,int L,int R)

{

    if(L == R) maxv[rt] = val[L];

    else

    {

        build(lson); build(rson);

        pushup(rt);

    }

}

void update(int rt,int L,int R)

{

    if(L == R) maxv[rt] = v;

    else {

        if(tar <= M) update(lson);

        if(tar > M) update(rson);

        pushup(rt);

    }

}

int query(int rt,int L,int R)

{

    if(ql <= L && qr >= R) return maxv[rt];

    int lv = -INT_MAX,rv = -INT_MAX;

    if(ql <= M) lv = query(lson);

    if(qr > M) rv = query(rson);

    return max(lv,rv);

}

int main()

{

    int N,m;

    char cmd;

    while(~scanf("%d%d",&N,&m))

    {

        for(int i = 1;i <= N;i++)

        scanf("%d",val + i);

        build(root);

        for(int i = 1;i <= m;i++)

         {

            scanf(" %c",&cmd);

            if(cmd == 'Q')

             {

                scanf("%d%d",&ql,&qr);

                printf("%d\n",query(root));

            }

            else

            {

                scanf("%d%d",&tar,&v);

                update(root);

            }

        }

    }

    return 0;

}

　　

随机推荐

  1. mysql&colon; Illegal mix of collations &lpar;utf8&lowbar;unicode&lowbar;ci&comma;IMPLICIT&rpar; and &lpar;utf8&lowbar;general&lowbar;ci&comma;IMPLICIT&rpar; for operation &&num;39&semi;&equals; 的解决

    昨天把mysql里所有table的varchar字段的字符集,批量换成了utf8mb4/utf8mb4_unicode_ci ,以便能保存一些emoji火星文 , 结果有一个sql语句执行时,报错如下 ...

  2. &lbrack;Asp&period;net MVC&rsqb;Asp&period;net MVC5系列——添加视图

    目录 系列文章 概述 添加视图 总结 系列文章 [Asp.net MVC]Asp.net MVC5系列——第一个项目 概述 在这一部分我们添加一个新的控制器HelloWorldController类, ...

  3. UIView常见属性总结

    一 UIVIew 常见属性 .frame 位置和尺寸(以父控件的左上角为原点(,)) .center 中点 (以父控件的左上角为原点(,)) .bounds 位置和尺寸(以自己的左上角为原点 (,)) ...

  4. ACM OJ Collection

    浙江大学(ZJU):http://acm.zju.edu.cn/ 北京大学(PKU):http://acm.pku.edu.cn/JudgeOnline/ 同济大学(TJU):http://acm.t ...

  5. js验证中英文

    // 验证中英文 function check_en_ch(_value){ var reg_en_num = /^[0-9A-Za-z\'\"\,\.\!\?\:\s|“|”|‘|’|!| ...

  6. 进入IT行业，你后悔过吗？

    问:你曾后悔进入 IT 行业吗?为什么? 也许你后悔做了IT,但是很希望你能用自己混IT界的惨痛经历给题主这样的后来人提个醒. 也许你庆幸做了IT,同样很希望能够看到同行朋友们的真诚交流. miao ...

  7. windows 下一个mysql password忘记改变

    到场mysql简介 my.ini 于[mysqld]以下被加入 skip-grant-tables win+R 热键 进cmd 然后输入命令net stop mysql  最后一点,使文件夹mysql ...

  8. nodejs-QQ空间灌水

    在本地编写javascript代码,node环境下命令行内运行,请求网页实现给QQ好友留言. 1.登录QQ空间,给好友留言,在开发者工具中打开网络面板,在network中找到addXXX开头的请求. ...

  9. 使用Redis数据库（1）（三十三）

    Spring Boot中除了对常用的关系型数据库提供了优秀的自动化支持之外,对于很多NoSQL数据库一样提供了自动化配置的支持,包括:Redis, MongoDB, Elasticsearch, So ...

  10. MySQL主从同步和半同步配置

    mysql主从配置: 1,安装maraidb,使用国内yum镜像站下载:[root@localhost mysql]# cat /etc/yum.repos.d/MairaDB.repo # Mari ...

相关文章