#include <bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <stack>

#include <set>

#include <cctype>

#define eps 1e-8

#define INF 0x3f3f3f3f

#define MOD 1e9+7

#define PI acos(-1)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 1e5 + ;

int n, q;

int MIN[maxn << ];//记录区间最小值

int lazy[maxn << ];//延迟标记减法

int ans[maxn << ];//记录答案数量

int b[maxn << ];//记录b数组

//线段树基本操作,pushup和pushdown

void pushup(int rt) {

    MIN[rt] = min(MIN[rt << ], MIN[rt <<  | ]);

    ans[rt] = ans[rt << ] + ans[rt <<  | ];

}

void pushdown(int rt) {

    if(lazy[rt]) {

        lazy[rt << ] += lazy[rt];

        lazy[rt <<  | ] += lazy[rt];

        MIN[rt << ] -= lazy[rt];

        MIN[rt <<  | ] -= lazy[rt];

        lazy[rt] = ;

    }

}

//建树

void build(int l, int r, int rt) {

    lazy[rt] = ;

    ans[rt] = ;

    if(l == r) {

        scanf("%d", &b[rt]);

        MIN[rt] = b[rt];

        return ;

    }

    int m = (l + r) >> ;

    build(lson);

    build(rson);

    pushup(rt);

}

//区间更新,需要注意当NIN减为0的时候,要ans++并且重新将b的值赋给MIN

void updata(int L, int R, int l, int r, int rt) {

    if(L <= l && R >= r) {

        MIN[rt]--;

        if(MIN[rt]) {

            lazy[rt]++;

            return;

        } else {

            if(l == r) {

                ans[rt]++;

                MIN[rt] = b[rt];

                return;

                /*血的教训,这个return不能放大括号外面,因为如果递归到某个节点MIN是0

                但是又不是叶子节点,那么还是需要继续递归直到找到叶子节点为止

                */

            }

        }

    }

    pushdown(rt);

    int m = (l + r) >> ;

    if(L <= m) updata(L, R, lson);

    if(R > m) updata(L, R, rson);

    pushup(rt);

}

//查询

int query(int L, int R, int l, int r, int rt) {

    if(L <= l && R >= r) {

        return ans[rt];

    }

    pushdown(rt);

    int m = (l + r) >> ;

    int sum = ;

    if(m >= L) sum += query(L, R, lson);

    if(m < R) sum += query(L, R, rson);

    return sum;

}

int main() {

    while(~scanf("%d%d", &n, &q)) {

        build(, n, );

        for(int i = ; i <= q; i++) {

            char op[];

            int a, b;

            scanf("%s%d%d", op, &a, &b);

            if(op[] == 'q') {

                printf("%d\n", query(a, b, , n, ));

            } else {

                updata(a, b, , n, );

            }

        }

    }

    return ;

}

复制来的代码

#include<queue>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

const int maxn = 1e5 + ;

int add[maxn << ];

int tree[maxn << ];

int MAX[maxn << ];

int a[maxn];

void build(int l, int r,int rt)

{

    add[rt] = ;

    MAX[rt] = (int)-1e9;

    tree[rt] = ;

    if (l == r){

        add[rt] = ;

        tree[rt] = ;

        MAX[rt] = -a[l];

        return;

    }

    int m = (l + r) >> ;

    build(lson);

    build(rson);

    tree[rt] = tree[rt << ] + tree[rt <<  | ];

    MAX[rt] = max(MAX[rt << ], MAX[rt <<  | ]);

}

void PushDown(int rt)

{

    if (add[rt]){

        add[rt << ] += add[rt];

        add[rt <<  | ] += add[rt];

        MAX[rt << ] += add[rt];

        MAX[rt <<  | ] += add[rt];

        add[rt] = ;

    }

}

void update1(int L, int R, int l, int r, int rt)

{

    if (L <= l&&r <= R){

        add[rt]++;

        MAX[rt]++;

        return;

    }

    PushDown(rt);

    int m = (l + r) >> ;

    if (L <= m)update1(L, R, lson);

    if (R > m)update1(L, R, rson);

    tree[rt] = tree[rt << ] + tree[rt <<  | ];

    MAX[rt] = max(MAX[rt << ], MAX[rt <<  | ]);

}

void update2(int L, int R, int l, int r, int rt)

{

    if (l == r){

        if (MAX[rt] >= ){

            tree[rt]++;

            MAX[rt] = -a[l];

        }

        return;

    }

    PushDown(rt);

    int m = (l + r) >> ;

    if (L <= m&&MAX[rt << ] >= )update2(L, R, lson);

    if (R > m&&MAX[rt <<  | ] >= )update2(L, R, rson);

    tree[rt] = tree[rt << ] + tree[rt <<  | ];

    MAX[rt] = max(MAX[rt << ], MAX[rt <<  | ]);

}

int query(int L, int R, int l, int r, int rt)

{

    if (L <= l&&r <= R){

        return tree[rt];

    }

    int m = (l + r) >> , ans = ;

    if (L <= m)ans += query(L, R, lson);

    if (R > m)ans += query(L, R, rson);

    return ans;

}

void Print(int l, int r, int rt)

{

    if (l == r){

        cout << rt << " = " << MAX[rt] << endl;

        return;

    }

    cout << rt << " = " << MAX[rt] << endl;

    int m = (l + r) >> ;

    if (l <= m)Print(lson);

    if (r > m)Print(rson);

}

int main()

{

    std::ios::sync_with_stdio(false);

    int n, q;

    while (cin >> n >> q){

        for (int i = ; i <= n; i++)

            cin >> a[i];

        build(, n, );

        string flag; int l, r;

        for (int i = ; i < q; i++){

            cin >> flag >> l >> r;

            if (flag == "add"){

                update1(l, r, , n, );

                update2(l, r, , n, );

                //Print(1, n, 1);

            }

            else cout << query(l, r, , n, ) << endl;

        }

    }

    return ;

}