题目链接

// Problem: Gorgeous Sequence
// Contest: Virtual Judge - HDU
// URL: https://vjudge.net/problem/HDU-5306
// Memory Limit: 128 MB
// Time Limit: 3000 ms
// Date: 2024/12/22 21:49:11
// Author: Li_Feiy

#include <bits/stdc++.h>
#define arrout(a, n) rep(i, 1, n) printk(a[i])
#define arrin(a, n) rep(i, 1, n) a[i] = read()
#define rep(i, x, n) for(int i = x; i <= n; i++)
#define dep(i, x, n) for(int i = x; i >= n; i--)
#define erg(i, x) for(int i = head[x]; i; i = e[i].nex)
#define dbg(x) std::cout << #x << ":" << x << " "
#define mem(a, x) memset(a, x, sizeof a)
#define all(x) x.begin(), x.end()
#define arrall(a, n) a + 1, a + 1 + n
#define PII std::pair<int, int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
int read() {
	char ch = getchar();
	int r = 0, w = 1;
	while(ch < '0' || ch > '9') w = ch == '-' ? -1 : w, ch = getchar();
	while(ch >= '0' && ch <= '9') r = (r << 3) + (r << 1) + (ch ^ 48), ch = getchar();
	return r * w;
}

void print(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) print(x / 10);
	putchar(x % 10 + '0');
}template<typename ...Args>
void print(int t, Args... args) { print(t), print(args...); }

void printl(int x) { print(x), putchar('\n'); }
template<typename ...Args>
void printl(int t, Args... args) { printl(t), printl(args...); }

void printk(int x) { print(x), putchar(' '); }
template<typename ...Args>
void printk(int t, Args ... args) { printk(t), printk(args...); }

CI N = 1e6 + 5;
int T, n, q, a[N];
struct Segment_Tree {
#define ls k << 1
#define rs k << 1 | 1
	struct SegTrr_Node {
		int ma, cnt, sec, sum, lazy;
	} s[N << 2];
	void pushup(int k) {
		s[k].ma = std::max(s[ls].ma, s[rs].ma);
		if(s[ls].ma > s[rs].ma) s[k].cnt = s[ls].cnt, s[k].sec = std::max(s[rs].sec, s[ls].ma);
		else if(s[ls].ma < s[rs].ma) s[k].cnt = s[rs].cnt, s[k].sec = std::max(s[ls].sec, s[rs].ma);
		else s[k].cnt = s[ls].cnt + s[rs].cnt, s[k].sec = std::max(s[ls].sec, s[rs].sec);
		s[k].sum = s[ls].sum + s[rs].sum;
	}
	void pushdown(int k, int l, int r) {
		if(~s[k].lazy) {
			int v = s[k].lazy;
			// Left
			if(s[ls].ma > v) {
				s[ls].sum -= s[ls].cnt * (s[ls].ma - v);
				s[ls].ma = s[ls].lazy = v;
			}
			// Right
			if(s[rs].ma > v) {
				s[rs].sum -= s[rs].cnt * (s[rs].ma - v);
				s[rs].ma = s[rs].lazy = v;
			}
			// Reset
			s[k].lazy = -1;
		}
	}
	void build(int k = 1, int l = 1, int r = n) {
		s[k].lazy = -1;
		if(l == r) {
			s[k].ma = s[k].sum = a[l], s[k].cnt = 1, s[k].sec = -1;
			return ;
		}
		int mid = l + r >> 1;
		build(ls, l, mid), build(rs, mid + 1, r);
		pushup(k);
	}
	void update(int x, int y, int v, int k = 1, int l = 1, int r = n) {
		if(y < l || x > r || s[k].ma <= v) return ;
		if(x <= l && r <= y && s[k].sec < v) {
			s[k].sum -= s[k].cnt * (s[k].ma - v), s[k].ma = s[k].lazy = v;
			return ;
		}
		int mid = l + r >> 1;
		pushdown(k, l, r);
		if(x <= mid) update(x, y, v, ls, l, mid);
		if(y > mid) update(x, y, v, rs, mid + 1, r);
		pushup(k);
	}
	int query_max(int x, int y, int k = 1, int l = 1, int r = n) {
		if(x <= l && r <= y) return s[k].ma;
		int mid = l + r >> 1, ans = -1;
		pushdown(k, l, r);
		if(x <= mid) ans = std::max(ans, query_max(x, y, ls, l, mid));
		if(y > mid) ans = std::max(ans, query_max(x, y, rs, mid + 1, r));
		return ans;
	}
	int query_sum(int x, int y, int k = 1, int l = 1, int r = n) {
		if(x <= l && r <= y) return s[k].sum;
		int mid = l + r >> 1, ans = 0;
		pushdown(k, l, r);
		if(x <= mid) ans += query_sum(x, y, ls, l, mid);
		if(y > mid) ans += query_sum(x, y, rs, mid + 1, r);
		return ans;
	}
#undef ls
#undef rs
} st;
signed main() {
	T = read();
	while(T --) {
		n = read(), q = read();
		arrin(a, n);
		st.build();
		while(q --) {
			int op = read(), l = read(), r = read();
			if(op == 0) st.update(l, r, read());
			else if(op == 1) printl(st.query_max(l, r));
			else printl(st.query_sum(l, r));
		}
	}
	return 0;
}