I hate it
2024-10-19 04:32:22
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。
在每个测试的第一行,有两个正整数 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处的值;
给定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;
}
最新文章
- SDK
- 内存缓存LruCache实现原理
- SharePoint excel service web part 连接到 filter web part
- JAVA NIO 真正做到处理一个事件
- struts.xml语法
- python多继承中子类访问祖先类的同名成员
- JRE vs OpenJDK vs Oracle JDK
- Vue 项目架构设计与工程化实践
- 195 Tenth Line
- 弹出层框架layer快速使用
- php实现cookie加密解密
- Hdu1896 Stones(优先队列) 2017-01-17 13:07 40人阅读 评论(0) 收藏
- 用 node.js 的 hexo 框架搭建一个支持 markdown 的静态博客系统
- centos7 install k8s centos 安装 kubernetes 详细
- 【Docker 命令】- kill命令
- 十二道MR习题 - 4 - TopN问题
- [YNOI2017][bzoj4811][luogu3613] 由乃的OJ/睡觉困难综合症 [压位+树链剖分+线段树]
- leetcode 【 Convert Sorted List to Binary Search Tree 】python 实现
- sublime text 3和sublime text 2的 package control 插件 代码
- 关于jQuery中的$发生冲突及解决方案