UESTC 1324线段树

某日，百无聊赖的卿学姐打开了某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<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000007 #define esp 0.00000000001 const 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<t;i++) { int flag; scanf("%d",&flag); if(flag==1) { int p; ll c; scanf("%d%lld",&p,&c); update(p,c,1,x,1); } else { int u,v; scanf("%d%d",&u,&v); printf("%lld\n",query(u,v,1,x,1)); } } } return 0; }