思路：
吉司机线段树
维护最大值和次大值，大于最大值不改，在最大值和次大值之间的直接修改，小于次大值递归修改。
代码：
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r //#define mp make_pair #define pb push_back #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdi pair<double, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head inline int read() { int a = 1, b = 0; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') a = -1; ch = getchar(); } while('0' <= ch && ch <= '9') { b = b*10 + ch-'0'; ch = getchar(); } return a*b; } const int N = 1e6 + 5; int a[N], mx[N<<2], cnt[N<<2], se[N<<2], lazy[N<<2], n, m, op, x, y, t, T; LL sum[N<<2]; inline void push_up(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; mx[rt] = max(mx[rt<<1], mx[rt<<1|1]); if(mx[rt<<1] > mx[rt<<1|1]) se[rt] = max(se[rt<<1], mx[rt<<1|1]), cnt[rt] = cnt[rt<<1]; else if(mx[rt<<1] < mx[rt<<1|1]) se[rt] = max(se[rt<<1|1], mx[rt<<1]), cnt[rt] = cnt[rt<<1|1]; else se[rt] = max(se[rt<<1], se[rt<<1|1]), cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1]; } inline void push_down(int rt) { if(lazy[rt] < mx[rt<<1]) sum[rt<<1] -= (mx[rt<<1] - lazy[rt])*1LL*cnt[rt<<1], mx[rt<<1] = lazy[rt], lazy[rt<<1] = lazy[rt]; if(lazy[rt] < mx[rt<<1|1]) sum[rt<<1|1] -= (mx[rt<<1|1] - lazy[rt])*1LL*cnt[rt<<1|1], mx[rt<<1|1] = lazy[rt], lazy[rt<<1|1] = lazy[rt]; lazy[rt] = 0; } void build(int rt, int l, int r) { lazy[rt] = 0; if(l == r) { sum[rt] = mx[rt] = a[l]; se[rt] = -1; cnt[rt] = 1; return ; } int m = l+r >> 1; build(ls); build(rs); push_up(rt); } void update(int L, int R, int x, int rt, int l, int r) { if(mx[rt] <= x) return ; if(L <= l && r <= R) { if(l == r) { sum[rt] = mx[rt] = x; se[rt] = -1; cnt[rt] = 1; return ; } if(se[rt] < x && x < mx[rt]) { sum[rt] -= (mx[rt] - x)*1LL*cnt[rt]; mx[rt] = x; lazy[rt] = x; } else { int m = l+r >> 1; if(lazy[rt]) push_down(rt); update(L, R, x, ls); update(L, R, x, rs); push_up(rt); } return ; } int m = l+r >> 1; if(lazy[rt]) push_down(rt); if(L <= m) update(L, R, x, ls); if(R > m) update(L, R, x, rs); push_up(rt); } LL querysum(int L, int R, int rt, int l, int r) { if(L <= l && r <= R) return sum[rt]; int m = l+r >> 1; LL ans = 0; if(lazy[rt]) push_down(rt); if(L <= m) ans += querysum(L, R, ls); if(R > m) ans += querysum(L, R, rs); push_up(rt); return ans; } int querymx(int L, int R, int rt, int l, int r) { if(L <= l && r <= R) return mx[rt]; int m = l+r >> 1; int ans = 0; if(lazy[rt]) push_down(rt); if(L <= m) ans = max(ans, querymx(L, R, ls)); if(R > m) ans = max(ans, querymx(L, R, rs)); push_up(rt); return ans; } int main() { T = read(); while(T--) { n = read(); m = read(); for (int i = 1; i <= n; ++i) a[i] = read(); build(1, 1, n); for (int i = 1; i <= m; ++i) { op = read(); if(op == 0) { x = read(); y = read(); t = read(); update(x, y, t, 1, 1, n); } else if(op == 1) { x = read(); y = read(); printf("%d ", querymx(x, y, 1, 1, n)); } else { x = read(); y = read(); printf("%lld ", querysum(x, y, 1, 1, n)); } } } return 0; }