本文共 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
转载地址:http://vjncf.baihongyu.com/