给你一个序列，支持三种操作：
$0\ x\ y\ t$ ：将 $[x,y]$ 内大于 $t$ 的数变为 $t$ ；
$1\ x\ y$ ：求 $[x,y]$ 内所有数的最大值；$2\ x\ y$ ：求 $[x,y]$ 内所有数的和。多组测试数据，$\sum n,\sum m\le 10^6$
题解
线段树区间最值操作
对于线段树上的一个节点，维护对应区间的：最大值 $mx$ 、最大值个数 $c$ 及严格次大值 $se$ 。那么对于一次区间最小值操作：
如果 $t\ge mx$ ，则这个操作不会对区间产生影响，直接退出；
如果 $se<t<mx$ ，则这个操作只会对区间最大值产生影响，区间和减小 $c(mx-t)$ ，最大值变为 $t$ ，打标记退出；否则，无法直接计算贡献，递归子树处理。其中第二种情况的 “打标记” 实际上就是下传新的最大值，因此可以不打标记，直接将最大值下传。
这样做的时间复杂度是 $O(n\log n)$ 的，证明参考
#include#include #define N 1000010#define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1using namespace std;typedef long long ll;ll mx[N << 2] , c[N << 2] , se[N << 2] , sum[N << 2];inline void vmin(ll v , int x){ if(mx[x] > v) sum[x] -= c[x] * (mx[x] - v) , mx[x] = v;}inline void pushup(int x){ int l = x << 1 , r = x << 1 | 1; sum[x] = sum[l] + sum[r]; if(mx[l] > mx[r]) mx[x] = mx[l] , c[x] = c[l] , se[x] = max(se[l] , mx[r]); if(mx[l] < mx[r]) mx[x] = mx[r] , c[x] = c[r] , se[x] = max(mx[l] , se[r]); if(mx[l] == mx[r]) mx[x] = mx[l] , c[x] = c[l] + c[r] , se[x] = max(se[l] , se[r]);}inline void pushdown(int x){ vmin(mx[x] , x << 1) , vmin(mx[x] , x << 1 | 1);}void build(int l , int r , int x){ if(l == r) { scanf("%lld" , &mx[x]) , sum[x] = mx[x] , c[x] = 1 , se[x] = -1; return; } int mid = (l + r) >> 1; build(lson) , build(rson); pushup(x);}void update(int b , int e , ll v , int l , int r , int x){ if(mx[x] <= v) return; if(b <= l && r <= e && se[x] < v) { vmin(v , x); return; } pushdown(x); int mid = (l + r) >> 1; if(b <= mid) update(b , e , v , lson); if(e > mid) update(b , e , v , rson); pushup(x);}ll qmax(int b , int e , int l , int r , int x){ if(b <= l && r <= e) return mx[x]; pushdown(x); int mid = (l + r) >> 1; ll ans = 0; if(b <= mid) ans = max(ans , qmax(b , e , lson)); if(e > mid) ans = max(ans , qmax(b , e , rson)); return ans;}ll qsum(int b , int e , int l , int r , int x){ if(b <= l && r <= e) return sum[x]; pushdown(x); int mid = (l + r) >> 1; ll ans = 0; if(b <= mid) ans += qsum(b , e , lson); if(e > mid) ans += qsum(b , e , rson); return ans;}int main(){ int T; scanf("%d" , &T); while(T -- ) { int n , m , opt , x , y; ll z; scanf("%d%d" , &n , &m); build(1 , n , 1); while(m -- ) { scanf("%d%d%d" , &opt , &x , &y); if(opt == 0) scanf("%lld" , &z) , update(x , y , z , 1 , n , 1); if(opt == 1) printf("%lld\n" , qmax(x , y , 1 , n , 1)); if(opt == 2) printf("%lld\n" , qsum(x , y , 1 , n , 1)); } } return 0;}