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
| #include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a,b,c) for(int a=(b),a##end=(c);a<=a##end;++a)
#define FR(a,b,c) for(int a=(b),a##end=(c);a>=a##end;--a)
#define lowbit(x) ((x)&-(x))
#define eb emplace_back
#define SZ(x) (int)((x).size())
#define int long long
#define vt vector
#define fr first
#define se second
#define ar(x) array<int,x>
#define PII pair<int, int>
#define max(a, b)({auto f7r=(a);auto j3h=(b);f7r<j3h?j3h:f7r;})
#define cmax(a, b)({auto j3h=(b);(j3h>a)&&(a=j3h);})
#define min(a, b)({auto f7r=(a);auto j3h=(b);f7r>j3h?j3h:f7r;})
#define cmin(a, b)({auto j3h=(b);(j3h<a)&&(a=j3h);})
constexpr int N = 5e5 + 10;
int n, m, a[N];
#define sgindex(l, r) ((l)+(r)|(l)!=(r))
#define u sgindex(l,r)
#define ls sgindex(l,sgm)
#define rs sgindex(sgm+1,r)
#define sgm (l+r>>1)
#define ln l,sgm
#define rn sgm+1,r
struct A{
int sum, ma, mi, cov, del;
A(int s=0, int m=0, int i=0, int z=0, int k=0):
sum(s), ma(m), mi(i){cov = del = 0;}
}w[N];
void chan(int l, int r, int v, int t){
if(t)w[u].sum -= (r - l + 1) * v, w[u].ma -= v, w[u].mi -= v, w[u].del += v;
else w[u].del = 0, w[u].cov = w[u].ma = w[u].mi = v,
w[u].sum = v * (r - l + 1);
}
void pushdown(int l, int r){
if(w[u].cov)chan(ln, w[u].cov, 0), chan(rn, w[u].cov, 0), w[u].cov = 0;
if(w[u].del)chan(ln, w[u].del, 1), chan(rn, w[u].del, 1), w[u].del = 0;
}
void pushup(int l, int r){
w[u] = A(w[rs].sum + w[ls].sum, max(w[rs].ma, w[ls].ma), min(w[rs].mi, w[ls].mi));
}
#define flo(x) floor(sqrt(x))
void change(int l, int r){
if(flo(w[u].ma) == flo(w[u].mi))return chan(l, r, flo(w[u].mi), 0);
if(w[u].ma - w[u].mi > 1)return pushdown(l, r), change(ln), change(rn), pushup(l, r);
chan(l, r, w[u].mi - flo(w[u].mi), 1);
}
void modify(int l, int r, int L, int R){
if(r < L || l > R)return;
if(L <= l && r <= R)return change(l, r);
pushdown(l, r), modify(ln, L, R), modify(rn, L, R), pushup(l, r);
}
void modify(int l, int r, int L, int R, int v){
if(r < L || l > R)return;
if(L <= l && r <= R)return chan(l, r, -v, 1);
pushdown(l, r), modify(ln, L, R, v), modify(rn, L, R, v), pushup(l, r);
}
int query(int l, int r, int L, int R){
if(L <= l && r <= R)return w[u].sum;
pushdown(l, r);
if(R <= sgm)return query(ln, L, R);
if(sgm < L)return query(rn, L, R);
return query(ln, L, R) + query(rn, L, R);
}
void build(int l, int r){
w[u] = A();
if(l == r)return chan(l, r, a[l], 0);
build(ln), build(rn), pushup(l, r);
}
#undef ls
#undef rs
#undef u
void solve(){
cin >> n >> m;
FL(i, 1, n)cin >> a[i];
build(1, n);
while(m--){
int op, l, r, x;
cin >> op >> l >> r;
if(op == 1)cin >> x, modify(1, n, l, r, x);
else if(op == 2)modify(1, n, l, r);
else cout << query(1, n, l, r) << endl;
}
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while(t--)solve();
return 0;
}
|
