某日，百无聊赖的卿学姐打开了某11区的某魔幻游戏

在这个魔幻的游戏里，生活着一个美丽的公主，但现在公主被关押在了魔王的城堡中。

英勇的卿学姐拔出利刃冲向了拯救公主的道路。

走过了荒野，翻越了高山，跨过了大洋，卿学姐来到了魔王的第一道城关。

在这个城关面前的是魔王的精锐部队，这些士兵成一字排开。

卿学姐的武器每次只能攻击一个士兵，并造成一定伤害，卿学姐想知道某时刻从L
到R

这个区间内，从开始到现在累计受伤最严重的士兵受到的伤害。

最开始每个士兵的受到的伤害都是0
Input

第一行两个整数N,Q
表示总共有N个士兵编号从1到N，和Q

个操作。

接下来Q
行，每行三个整数，首先输入一个t，如果t是1，那么输入p,x，表示卿学姐攻击了p这个位置的士兵，并造成了x的伤害。如果t是2，那么输入L,R，表示卿学姐想知道现在[L,R]

闭区间内，受伤最严重的士兵受到的伤害。

1≤N≤100000

1≤Q≤100000

1≤p≤N

1≤x≤100000

1≤L≤R≤N

Output

对于每个询问，回答相应的值
Sample input and output
Sample Input Sample Output

5 4
2 1 2
1 2 4
1 3 5
2 3 3

0
5

解题方法： 复习分块，从明天开始开一个分块法的专题，给代码吧，讲解在blibli上有,模仿qsc写的。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int belong[maxn], num, l[maxn], r[maxn];
int n, q, block;
long long a[maxn], Max[maxn];
//num 分块的个数
//block 块的大小
//belong[i]表示i属于哪一块
//l[i]表示i这块的左端点位置
//r[i]表示i这块的右端点位置
void build(){
    block = sqrt(n);
    num = n / block;
    if(n % block) num++;
    for(int i = 1; i <= num; i++){
        l[i] = (i - 1)*block + 1, r[i] = i*block;
    }
    r[num] = n;
    for(int i = 1; i <= n; i++){
        belong[i] = (i - 1)/block + 1;
    }
    for(int i = 1; i <= num; i++){
        for(int j = l[i]; j <= r[i]; j++){
            Max[i] = max(Max[i], a[j]);
        }
    }
}
void update(int x, int y){
    a[x] += y;
    Max[belong[x]] = max(Max[belong[x]], a[x]);
}
long long query(int x, int y){
    long long ans = 0;
    if(belong[x] == belong[y]){
        for(int i = x; i <= y; i++){
            ans = max(ans, a[i]);
        }
        return ans;
    }
    for(int i = x; i <= r[belong[x]]; i++){
        ans = max(ans, a[i]);
    }
    for(int i = belong[x] + 1; i < belong[y]; i++){
        ans = max(ans, Max[i]);
    }
    for(int i = l[belong[y]]; i <= y; i++){
        ans = max(ans, a[i]);
    }
    return ans;
}
int main(){
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= q; i++){
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1) update(l, r);
        else printf("%lld\n", query(l, r));
    }
    return 0;
}