UESTC 1324线段树
发布日期:2021-06-29 21:39:39
浏览次数:3
分类:技术文章
本文共 1584 字,大约阅读时间需要 5 分钟。
某日,百无聊赖的卿学姐打开了某11区的某魔幻游戏 在这个魔幻的游戏里,生活着一个美丽的公主,但现在公主被关押在了魔王的城堡中。 英勇的卿学姐拔出利刃冲向了拯救公主的道路。 走过了荒野,翻越了高山,跨过了大洋,卿学姐来到了魔王的第一道城关。 在这个城关面前的是魔王的精锐部队,这些士兵成一字排开。 卿学姐的武器每次只能攻击一个士兵,并造成一定伤害,卿学姐想知道某时刻从LL到RR这个区间内,从开始到现在累计受伤最严重的士兵受到的伤害。 最开始每个士兵的受到的伤害都是0 Input 第一行两个整数N,QN,Q表示总共有NN个士兵编号从11到NN,和QQ个操作。 接下来QQ行,每行三个整数,首先输入一个tt,如果tt是11,那么输入p,xp,x,表示卿学姐攻击了pp这个位置的士兵,并造成了xx的伤害。如果tt是22,那么输入L,RL,R,表示卿学姐想知道现在[L,R][L,R]闭区间内,受伤最严重的士兵受到的伤害。 1≤N≤1000001≤N≤100000 1≤Q≤1000001≤Q≤100000 1≤p≤N1≤p≤N 1≤x≤1000001≤x≤100000 1≤L≤R≤N1≤L≤R≤N Output 对于每个询问,回答相应的值 Sample Input 5 4 2 1 2 1 2 4 1 3 5 2 3 3 Sample Output 0 5 Hint注意可能会爆int哦
代码:
#includeusing namespace std;#define ll long long#define mod 1000000007#define esp 0.00000000001const int N=2e5+10,M=1e6+10,inf=1e9;ll maxx[N<<2];void buildtree(int l,int r,int pos){ if(l==r) { maxx[pos]=0; return; } int mid=(l+r)>>1; buildtree(l,mid,pos<<1); buildtree(mid+1,r,pos<<1|1); maxx[pos]=max(maxx[pos<<1],maxx[pos<<1|1]);}void update(int p,ll c,int l,int r,int pos){ if(l==p&&r==p) { maxx[pos]+=c; return; } int mid=(l+r)>>1; if(p>mid) update(p,c,mid+1,r,pos<<1|1); else update(p,c,l,mid,pos<<1); maxx[pos]=max(maxx[pos<<1],maxx[pos<<1|1]);}ll query(int L,int R,int l,int r,int pos){ if(L<=l&&R>=r) return maxx[pos]; int mid=(l+r)>>1; ll ans=0; if(L<=mid) ans=max(ans,query(L,R,l,mid,pos<<1)); if(R>mid) ans=max(ans,query(L,R,mid+1,r,pos<<1|1)); return ans;}int main(){ int x,y,i,t; while(~scanf("%d%d",&x,&t)) { buildtree(1,x,1); for(i=0;i
转载地址:https://dh-butterfly.blog.csdn.net/article/details/70168225 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月29日 08时16分33秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
基础架构系列篇-系统centos7安装docker+COMPOSE
2019-04-30
基础架构系列篇-系统centos7中docker安装rabbitmq
2019-04-30
基础架构系列篇-NGINX部署VUE
2019-04-30
个人电商项目,基于uni-app+ springcloud +VUE技术
2019-04-30
基础架构系列篇-系统centos7安装kafka
2019-04-30
基础架构系列篇-系统centos7中docker安装分布式文件存储服务minio
2019-04-30
知识点记录-java判断系统是linux或windows
2021-07-03
知识点记录-springboot静态资源映射路径
2021-07-03
知识点记录-vue-cli+webpack打包运行图标显示异常
2021-07-03
知识点记录-springboot2.1集成rabbitmq
2021-07-03
微服务springcloud2系列篇-配置与注册nacos组件
2021-07-03
数据库系列篇mysql8-分库分表中间件mycat(WINDOWS环境)
2021-07-03
用户权限设计-基于RBAC模型
2021-07-03
微服务springcloud2系列篇-网关GATEWAY跨域问题
2021-07-03
Java并发以及多线程基础
2021-07-03
软件质量的8个特性
2021-07-03
应届渣渣前端的艰难求职之路
2021-07-03