Hdu1754-线段树-单点更新
2023-03-14 10:16:55 时间
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn=200005; int MAX[maxn<<2]; void pushup(int rt) { MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]); } void build(int l,int r,int rt) { if(l==r) { scanf("%d",&MAX[rt]); return; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt); } void update(int p ,int x, int l,int r,int rt) { if(l==r) { MAX[rt]=x; return; } int m=(l+r)>>1; if(p<=m) update(p,x,lson); else update(p,x,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l && R>=r) return MAX[rt]; int m=(r+l)>>1; int ans=0; if(L<=m) ans=max(query(L,R,lson),ans); if(R>m) ans=max(query(L,R,rson),ans); return ans; } int main() { int n,m; while( scanf("%d %d",&n,&m)!=EOF) { build(1,n,1); char s[2]; while(m--) { int a,b; scanf("%s%d%d",s,&a,&b); if(s[0]=='Q') printf("%d\n",query(a,b,1,n,1)); else if(s[0]=='U') update(a,b,1,n,1); } } return 0; }
相关文章
- 非科班出身的人学习编程不负责任指南
- PHP 8.1新特性公布 增加 Enums、Fsync功能
- 什么时候应该避免注释代码?
- 现在写 PHP,你应该知道这些
- 居然还能这样——程序员加薪的新方法
- 程序员不要输在起跑线上 这4个问题帮你迅速入行
- 怎样提高开发效率?关于增效,需要做好这两点
- 新一轮互联网的泡沫将破灭,大量低级别的码农面临淘汰
- 坐着编程变胖 站着编程伤膝盖
- 不懂技术的人不要对懂技术的人说这很容易实现
- 如何在中国打造拥有谷歌工程师文化的团队
- 什么时候应该避免注释代码
- 教你如何在 Linux 中锁定和解锁多个用户
- 排序之简单选择排序
- 什么是Javascript Hoisting?
- 创业是一场游戏,会玩的人才会赢
- 以一当十的程序员不是传说
- 程序员如何既不耽误工作又有时间干业余项目?
- 掌握微服务下分布式锁的正确姿势
- 编码之道:取个好名字很重要