单侧递归线段树能高效维护前后缀最值有关的信息。

显然 $1$ 操作影响的是前缀最大值位置。

建立线段树，每个节点维护 $H$ 的最大值 $m$，前缀最大值个数 $c$，$S$ 的和 $s$。

考虑 pushup，$c_\text{ls}$ 可以直接用，但对于 $\text{rs}$ 需要满足值 $\ge x=m_\text{ls}$ 才行，考虑递归下去。设当前到 $u$，若 $m_\text{ls}\le x$，则递归 $\text{rs}$，否则递归 $\text{ls}$ 并加上 $\text{rs}$ 中值 $\ge m_\text{ls}$ 的部分，即 $c_u-c_\text{ls}$。

对于 $1$ 操作，考虑维护标记 $\text{t}$，apply 时更新 $u$ 中 $\ge m_\text{ls}$ 的位置，pushdown 时下放到 $\text{rs}$。这个不能简单 apply，类似上面的方法递归下去即可。执行 $1$ 操作时维护当前前缀最大值 $x$，对于拆出的 $O(\log n)$ 个区间递归即可。

对于 $3$ 操作，再维护一个标记 $h$ 即可，递归时要下传 $h$，不影响复杂度。

显然单次递归是 $O(\log n)$ 的，复杂度为 $O(n\log n+q\log^2 n)$。

::::info[code]

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

#define ls (u << 1)
#define rs (u << 1 | 1)

struct SGT {
	struct Node { i64 mx, cmx, sum, add, tag; };
	int n; vector<Node> tr;
	
	void pull(int u, int l, int r) {
		int mid = (l + r) >> 1;
		tr[u].mx = max(tr[ls].mx, tr[rs].mx);
		tr[u].sum = tr[ls].sum + tr[rs].sum;
		tr[u].cmx = tr[ls].cmx + calc(rs, mid + 1, r, tr[ls].mx);
	}
	
	void pushadd(int u, i64 v) {
		tr[u].mx += v, tr[u].add += v;
	}
	
	void pushtag(int u, int l, int r, i64 mx, i64 v) {
		if (tr[u].mx <= mx) return;
		if (l == r) {
			tr[u].sum += v * tr[u].cmx, tr[u].tag += v;
			return;
		}
		if (tr[u].add) {
			pushadd(ls, tr[u].add);
			pushadd(rs, tr[u].add);
			tr[u].add = 0;
		}
		
		int mid = (l + r) >> 1;
		if (tr[ls].mx <= mx) {
			i64 lst = tr[rs].sum;
			pushtag(rs, mid + 1, r, mx, v);
			tr[u].sum += tr[rs].sum - lst;
		}
		else {
			tr[u].tag += v, tr[u].sum += v * (tr[u].cmx - tr[ls].cmx);
			i64 lst = tr[ls].sum;
			pushtag(ls, l, mid, mx, v);
			tr[u].sum += tr[ls].sum - lst;
		}
	}
	
	void push(int u, int l, int r) {
		int mid = (l + r) >> 1;
		if (tr[u].add) {
			pushadd(ls, tr[u].add);
			pushadd(rs, tr[u].add);
			tr[u].add = 0;
		}
		if (tr[u].tag) {
			pushtag(rs, mid + 1, r, tr[ls].mx, tr[u].tag);
			tr[u].tag = 0;
		}
	}
	
	void build(int u, int l, int r, const vector<int>& h) {
		if (l == r) {
			tr[u].mx = h[l];
			tr[u].cmx = 1;
			return;
		}
		
		int mid = (l + r) >> 1;
		build(ls, l, mid, h);
		build(rs, mid + 1, r, h);
		pull(u, l, r);
	}
	
	i64 calc(int u, int l, int r, i64 mx) {
		if (tr[u].mx <= mx) return 0;
		if (l == r) return 1;
		if (tr[u].add) {
			pushadd(ls, tr[u].add);
			pushadd(rs, tr[u].add);
			tr[u].add = 0;
		}
		
		int mid = (l + r) >> 1;
		if (tr[ls].mx <= mx) return calc(rs, mid + 1, r, mx);
		else return calc(ls, l, mid, mx) + tr[u].cmx - tr[ls].cmx;
	}
	
	void addh(int u, int l, int r, int L, int R, i64 v) {
		if (r < L || R < l) return;
		if (L <= l && r <= R) { pushadd(u, v); return; }
		int mid = (l + r) >> 1;
		push(u, l, r);
		addh(ls, l, mid, L, R, v);
		addh(rs, mid + 1, r, L, R, v);
		pull(u, l, r);
	}
	
	void add(int u, int l, int r, int L, int R, i64 &mx) {
		if (r < L || R < l) return;
		if (L <= l && r <= R) {
			pushtag(u, l, r, mx, 1);
			chmax(mx, tr[u].mx);
			return;
		}
		int mid = (l + r) >> 1;
		push(u, l, r);
		add(ls, l, mid, L, R, mx);
		add(rs, mid + 1, r, L, R, mx);
		pull(u, l, r);
	}
	
	i64 ask(int u, int l, int r, int L, int R) {
		if (r < L || R < l) return 0;
		if (L <= l && r <= R) return tr[u].sum;
		int mid = (l + r) >> 1;
		push(u, l, r);
		return ask(ls, l, mid, L, R) + ask(rs, mid + 1, r, L, R);
	}
	
	i64 get(int u, int l, int r, int x) {
		if (l == r) return tr[u].mx;
		int mid = (l + r) >> 1;
		push(u, l, r);
		if (x <= mid) return get(ls, l, mid, x);
		else return get(rs, mid + 1, r, x);
	}
	
	void addh(int l, int r, i64 v) { addh(1, 0, n - 1, l, r, v); }
	void add(int l, int r, i64 &mx) { add(1, 0, n - 1, l, r, mx); }
	i64 ask(int l, int r) { return ask(1, 0, n - 1, l, r); }
	i64 get(int x) { return get(1, 0, n - 1, x); }
	
	void init(const vector<int>& h) {
		n = (int)h.size();
		tr.assign(n << 2, {});
		build(1, 0, n - 1, h);
	}
} seg;

vector<i64> tower_events(vector<int> H, vector<vector<int>> E) {
	int n = (int)H.size();
	seg.init(H); vector<i64> ans;
	for (auto e : E) {
		if (e.size() == 1) {
			int x = e[0];
			i64 mx = seg.get(x);
			seg.add(x + 1, n - 1, mx);
		}
		
		if (e.size() == 2) {
			int l = e[0], r = e[1];
			ans.push_back(seg.ask(l, r));
		}
		
		if (e.size() == 3) {
			int l = e[0], r = e[1], v = e[2];
			seg.addh(l, r, v);
		}
	}
	return ans;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, q;
	cin >> n >> q;
	
	vector<int> H(n);
	for (int i = 0; i < n; i++) cin >> H[i];
	
	vector<vector<int>> E(q);
	for (int i = 0, t; i < q; i++) {
		cin >> t, E[i].resize(t);
		for (auto &x : E[i]) cin >> x;
	}
	
	auto ans = tower_events(H, E);
	for (auto x : ans) cout << x << '\n';
	
	return 0;
}