A - 卿学姐与公主
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
某日，百无聊赖的卿学姐打开了某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 and output
| Sample Input | Sample Output |
|---|---|
5 42 1 21 2 41 3 52 3 3 | 05 |
Hint
注意可能会爆int哦
#include#include #include using namespace std;const int N = 100000 + 5;typedef long long LL;LL T[N << 2];int M;void Build(int n){ for(M = 1; M <= n + 1; M *= 2);}void Updata(int n, int V){ for(T[n+=M] += V, n /= 2; n; n /= 2) T[n] = max(T[n << 1], T[n << 1|1]);}LL Query(int s, int t){ LL ans = 0; for(s=s+M-1, t=t+M+1; s^t^1; s/=2, t/=2){ if(~s&1) ans = max(ans, T[s^1]); if(t&1) ans = max(ans, T[t^1]); } return ans;}int main(){ int n, q; scanf("%d %d", &n, &q); Build( n ); int t, p, l, r, x; while(q --){ scanf("%d", &t); if(t == 1){ scanf("%d %d", &p, &x); Updata(p, x); }else{ scanf("%d %d", &l, &r); printf("%lld\n", Query(l, r)); } } return 0;}
#include#include #include using namespace std;#define lson l, m, rt << 1#define rson m + 1, r, rt << 1|1const int N = 100000 + 5;typedef long long LL;LL T[N << 2];void PushUP(int rt){ T[rt] = max(T[rt << 1], T[rt << 1|1]);}void Updata(int p, int c, int l, int r, int rt){ if(l == r){ T[rt] += c; return ; } int m = (l + r) >> 1; if(p <= m) Updata(p, c, lson); else Updata(p, c, rson); PushUP( rt );}LL Query(int L, int R, int l, int r, int rt){ if(L <= l && r <= R){ return T[rt]; } int m = (l + r) >> 1; LL ret = 0; if(L <= m) ret = max(ret, Query(L, R, lson)); if(R > m) ret = max(ret, Query(L, R, rson)); return ret;}int main(){ int n, q; scanf("%d %d", &n, &q); int t, p, l, r, x; while(q --){ scanf("%d", &t); if(t == 1){ scanf("%d %d", &p, &x); Updata(p, x, 1, n, 1); }else{ scanf("%d %d", &l, &r); printf("%lld\n", Query(l, r, 1, n, 1)); } } return 0;}