1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cerr << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cerr << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cerr << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cerr << a << ' '; err(args...); }
const int N = 1E6 + 100, INF = numeric_limits<int>::max();
int n;
const int BUF_SZ = 100000;
char buf[BUF_SZ + 10];
inline char nc() {
static char *pr = buf, *pend = buf;
if (pr == pend) {
pr = buf;
pend = pr + fread(buf, 1, BUF_SZ, stdin);
if (pr == pend) return EOF;
else return *pr++;
}
return *pr++;
}
template <typename T>
inline bool read(T& x) {
static char ch;
ch = nc();
while (ch != EOF && !isdigit(ch)) ch = nc();
if (ch == EOF) return false;
for (x = 0; isdigit(ch); ch = nc())
x = x * 10 + ch - '0';
return true;
}
namespace R {
#define lson o * 2, l, (l + r) / 2
#define rson o * 2 + 1, (l + r) / 2 + 1, r
int m1[N], m2[N], cm1[N];
LL sum[N];
void up(int o) {
int lc = o * 2, rc = lc + 1;
m1[o] = max(m1[lc], m1[rc]);
sum[o] = sum[lc] + sum[rc];
if (m1[lc] == m1[rc]) {
cm1[o] = cm1[lc] + cm1[rc];
m2[o] = max(m2[lc], m2[rc]);
} else {
cm1[o] = m1[lc] > m1[rc] ? cm1[lc] : cm1[rc];
m2[o] = max(min(m1[lc], m1[rc]), max(m2[lc], m2[rc]));
}
}
void mod(int o, int x) {
if (x >= m1[o]) return;
assert(x > m2[o]);
sum[o] -= 1LL * (m1[o] - x) * cm1[o];
m1[o] = x;
}
void down(int o) {
int lc = o * 2, rc = lc + 1;
mod(lc, m1[o]); mod(rc, m1[o]);
}
void build(int o, int l, int r) {
if (l == r) { int t; read(t); sum[o] = m1[o] = t; m2[o] = -1; cm1[o] = 1; }
else { build(lson); build(rson); up(o); }
}
void update(int ql, int qr, int x, int o, int l, int r) {
if (r < ql || qr < l || m1[o] <= x) return;
if (ql <= l && r <= qr && m2[o] < x) { mod(o, x); return; }
down(o);
update(ql, qr, x, lson); update(ql, qr, x, rson);
up(o);
}
int qmax(int ql, int qr, int o, int l, int r) {
if (r < ql || qr < l) return -INF;
if (ql <= l && r <= qr) return m1[o];
down(o);
return max(qmax(ql, qr, lson), qmax(ql, qr, rson));
}
LL qsum(int ql, int qr, int o, int l, int r) {
if (r < ql || qr < l) return 0;
if (ql <= l && r <= qr) return sum[o];
down(o);
return qsum(ql, qr, lson) + qsum(ql, qr, rson);
}
}
int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; read(T);
while (T--) {
int Qn; read(n); read(Qn);
R::build(1, 1, n);
while (Qn--) {
int tp, l, r; read(tp); read(l); read(r);
if (tp == 0) {
int x; read(x);
R::update(l, r, x, 1, 1, n);
} else if (tp == 1) {
printf("%d\n", R::qmax(l, r, 1, 1, n));
} else if (tp == 2) {
printf("%lld\n", R::qsum(l, r, 1, 1, n));
}
}
}
}
|