#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long i128;

class IO {
    char ibuf[1 << 16], obuf[1 << 16], *ipl = ibuf, *ipr = ibuf, *op = obuf;
    public:
    ~IO() { write(); }
    void read() { if (ipl == ipr) ipr = (ipl = ibuf) + fread(ibuf, 1, 1 << 15, stdin); }
    void write() { fwrite(obuf, 1, op - obuf, stdout), op = obuf; }
    char getchar() { return (read(), ipl != ipr) ? *ipl++ : EOF; }
    void putchar(char c) { *op++ = c; if (op - obuf > (1 << 15)) write(); }
    template <typename V> IO& operator >> (V& v) {
        int s = 1; char c = getchar(); v = 0;
        for (; !isdigit(c); c = getchar()) if (c == '-') s = -s;
        for (; isdigit(c); c = getchar()) v = (v << 1) + (v << 3) + (c ^ 48);
        return v *= s, *this;
    }
    IO& operator << (char c) { return putchar(c), *this; }
    template <typename V> IO& operator << (V v) {
        if (!v) putchar('0'); if(v < 0) putchar('-'), v = -v;
        char stk[100], *top = stk;
        for (; v; v /= 10) *++top = v % 10 + '0';
        while (top != stk) putchar(*top--); return *this;
    }
} io;
const int N = 5e5 + 5;
const ll lim = 1e18;
int tam[N << 2], tar[N << 2], mx[N << 2];
ll tag[N << 2], sum[N << 2], sr[N << 2];
i128 ans[N << 2];
int a[N];
void print(i128 x)
{
	io << (ll)x << '\n';
}
void work(int p, int l, int r, int k, int t) // subtree add max(k, premax)
{
	int mid = (l + r) >> 1;
	if(k >= mx[p])
	{
		tag[p] += (ll)k * t;
		ans[p] += (i128)k * t * (r - l + 1);
		return ;
	}
	if(l == r)
	{
		tam[p] += t;
		ans[p] += (i128)t * sum[p];
		return ;
	}
	if(k < mx[p << 1])
	{
		ans[p] -= ans[p << 1];
		work(p << 1, l, mid, k, t);
		tar[p] += t;
		ans[p] += ans[p << 1] + (i128)t * sr[p];
	}
	else
	{
		ans[p] -= ans[p << 1] + ans[p << 1 | 1];
		tag[p << 1] += (ll)k * t;
		ans[p << 1] += (i128)k * t * (mid - l + 1);
		work(p << 1 | 1, mid + 1, r, k, t);
		ans[p] += ans[p << 1] + ans[p << 1 | 1];
	}
	// ans[p] = ans[p << 1] + ans[p << 1 | 1] + (i128)tam[p] * sum[p] + (i128)tar[p] * sr[p] + (i128)tag[p] * (r - l + 1);
}
ll calc(int p, int l, int r, int k)
{
	int mid = (l + r) >> 1;
	if(k >= mx[p])
		return k * (r - l + 1ll);
	if(l == r)
		return sum[p];
	if(k < mx[p << 1])
		return calc(p << 1, l, mid, k) + sr[p];
	else
		return k * (mid - l + 1ll) + calc(p << 1 | 1, mid + 1, r, k);
}
void upd(int p, int l, int r, int q, int k)
{
	int mid = (l + r) >> 1;
	if(l == r)
	{
		tam[p] = 0;
		sum[p] = mx[p] = k;
		return ;
	}
	tam[p << 1] += tam[p];
	ans[p << 1] += (i128)tam[p] * sum[p << 1];
	work(p << 1 | 1, mid + 1, r, mx[p << 1], tam[p] + tar[p]);
	tam[p] = tar[p] = 0;
	if(q <= mid)
		upd(p << 1, l, mid, q, k);
	else
		upd(p << 1 | 1, mid + 1, r, q, k);
	sr[p] = calc(p << 1 | 1, mid + 1, r, mx[p << 1]);
	sum[p] = sum[p << 1] + sr[p];
	mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
	ans[p] = ans[p << 1] + ans[p << 1 | 1] + (i128)tag[p] * (r - l + 1);
}
void build(int p, int l, int r)
{
	int mid = (l + r) >> 1;
	tam[p] = tar[p] = tag[p] = ans[p] = 0;
	if(l == r)
	{
		sum[p] = mx[p] = a[l];
		return ;
	}
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	sr[p] = calc(p << 1 | 1, mid + 1, r, mx[p << 1]);
	sum[p] = sum[p << 1] + sr[p];
	mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
}
int add(int p, int l, int r, int ql, int qr, int k)
{
	int mid = (l + r) >> 1;
	if(ql <= l && r <= qr)
	{
		work(p, l, r, k, 1);
		return max(mx[p], k);
	}
	int qwq = 0;
	if(qr <= mid)
	{
		ans[p] -= ans[p << 1];
		qwq = add(p << 1, l, mid, ql, qr, k);
		ans[p] += ans[p << 1];
		return qwq;
	}
	if(ql > mid)
	{
		ans[p] -= ans[p << 1 | 1];
		qwq = add(p << 1 | 1, mid + 1, r, ql, qr, k);
		ans[p] += ans[p << 1 | 1];
		return qwq;
	}
	ans[p] -= ans[p << 1] + ans[p << 1 | 1];
	qwq = add(p << 1 | 1, mid + 1, r, ql, qr, add(p << 1, l, mid, ql, qr, k));
	ans[p] += ans[p << 1] + ans[p << 1 | 1];
	return qwq;
}
i128 qry(int p, int l, int r, int ql, int qr)
{
	int mid = (l + r) >> 1;
	if(ql <= l && r <= qr)
		return ans[p];
	int len = min(qr, r) - max(ql, l) + 1;
	tam[p << 1] += tam[p];
	ans[p << 1] += (i128)tam[p] * sum[p << 1];
	work(p << 1 | 1, mid + 1, r, mx[p << 1], tam[p] + tar[p]);
	tam[p] = tar[p] = 0;
	if(qr <= mid)
		return qry(p << 1, l, mid, ql, qr) + (i128)tag[p] * len;
	if(ql > mid)
		return qry(p << 1 | 1, mid + 1, r, ql, qr) + (i128)tag[p] * len;
	return qry(p << 1, l, mid, ql, qr) + qry(p << 1 | 1, mid + 1, r, ql, qr) + (i128)tag[p] * len;
}

int main()
{
	int n, q, i, t, l, r;
	io >> n >> q;
	for(i = 1; i <= n; i++)
		io >> a[i];
	build(1, 1, n);
	while(q--)
	{
		io >> t >> l >> r;
		if(t == 1)
			upd(1, 1, n, l, r);
		if(t == 2)
			add(1, 1, n, l, r, 0);
		if(t == 3)
			print(qry(1, 1, n, l, r));
	}
	return 0;
}