终于拿下了这棵线段树!!!!(哭)
#include
#define endl '\n'
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
typedef pair PII;
const int N = 1e5 + 10;
struct Tree
{int l, r;int max, cnt, lazy;
} tr[N << 2];
int w[N];
int n, m;
void change(int u, int lazy)
{tr[u].max += lazy;tr[u].lazy += lazy;
}
void pushdown(int u)
{if (tr[u].lazy){change(u << 1, tr[u].lazy);change(u << 1 | 1, tr[u].lazy);tr[u].lazy = 0;}
}
void pushup(Tree &u, Tree &l, Tree &r)
{u.max = max(l.max, r.max);if (l.max == r.max)u.cnt = l.cnt + r.cnt;else if (l.max > r.max)u.cnt = l.cnt;elseu.cnt = r.cnt;
}
void pushup(int u)
{pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{if (l == r){tr[u] = {l, r, w[l], 1, 0};}else{tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u);}
}
void modify(int u, int l, int r, int k)
{if (tr[u].l >= l && tr[u].r <= r){change(u, k);return;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid)modify(u << 1, l, r, k);if (r > mid)modify(u << 1 | 1, l, r, k);pushup(u);
}
Tree query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r)return tr[u];pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (r <= mid)return query(u << 1, l, r);else if (l > mid)return query(u << 1 | 1, l, r);else{auto left = query(u << 1, l, r);auto right = query(u << 1 | 1, l, r);Tree res;pushup(res, left, right);return res;}
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> w[i];}build(1, 1, n);int op, l, r, c;while (m--){cin >> op >> l >> r;if (op == 1){cin >> c;modify(1, l, r, c);}else{cout << query(1, l, r).cnt << endl;}}return 0;
}