博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UESTC 1324线段树
阅读量:1906 次
发布时间:2019-04-26

本文共 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哦

代码:

#include
using 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

转载地址:http://vjncf.baihongyu.com/

你可能感兴趣的文章
【Linux】vim的简单配置
查看>>
笔记本怎么设置WIfi热点
查看>>
Java面试题全集(上)
查看>>
Java面试题全集(中)
查看>>
值传递和引用传递
查看>>
什么是N+1查询?
查看>>
直插,快排,堆排,归并排序的分析
查看>>
二叉树的各种操作(面试必备)
查看>>
oracle
查看>>
Struts2中的session、request、respsonse获取方法
查看>>
如何理解MVC模型
查看>>
SpringMVC中乱码解决方案
查看>>
SpringMVC中时间格式转换的解决方案
查看>>
post和get请求相关知识点
查看>>
关于try finally 中的return语句的问题
查看>>
RequestBody/ResponseBody处理Json数据
查看>>
springmvc请求参数获取的几种方法
查看>>
Java中的IO流
查看>>
java中的关键字
查看>>
如果某个方法是静态的,它的行为就不具有多态性
查看>>