题目：
三种操作
0 l r t: 使这个区间的每个值变成min(t,a[i])。
1 l r: 输出区间最大值
2 l r: 输出区间和
(1 <= n,m <= 1e6, 0 <= ai,t <= 2^31)
分析：
1和2操作很简单，0操作很难，一个一个改时间肯定不允许，但是又没什么办法可以直接全改掉。
结合题目问的是区间最大值和区间和，那么就思考操作 0 会对区间最大值和区间和有什么影响，于是就有了以下方法：
维护 3 个值，区间最大值，区间严格次大值，区间最大值的个数。然后我们每次做0操作的时候，就会有3种情况。
- t >= 区间最大值, 这时每个值都不用修改，直接返回。
- 区间次大值 < t < 区间最大值，此时只有最大值会变，又已经求得了最大值的个数，所以我们可以直接更新这段的sum和max。
- 其他情况。无法直接对当前情况修改，所以继续搜两个儿子，直到搜到前两种情况为止。
我们可以把区间的最大值看做是这个区间的标记，因为每次更新的时候只会更新到（区间次大值 < t < 区间最大值）的情况，然后会修改sum和max，所以以后一旦进入这个区间的子树，必须先更新这个子树的max和sum。于是就有了pushdown()的写法，它就是负责把当前区间的sum和mx信息传给子树。
代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
#define ms(a,b) memset(a,b,sizeof(a))
#define lson rt*2,l,(l+r)/2
#define rson rt*2+1,(l+r)/2+1,r
typedef long long ll;
const int MAXN = 1e6 + 10;
const double EPS = 1e-8;
const int INF = 0x3f3f3f3f;
ll sum[MAXN << 2], mx[MAXN << 2], se[MAXN << 2], num[MAXN << 2];
int n, m;
void pushup(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], se[rt << 1 | 1]);
num[rt] = num[rt << 1] + num[rt << 1 | 1];
}
else {
//这个地方需要特别注意！因为一个子树的次大值有可能比另一个子树的最大值还要大。所以总的次大值不一定是哪个，需要都比较一下。debug了很久很久。。。
se[rt] = max(se[rt<<1],se[rt<<1|1]);
se[rt] = max(se[rt],min(mx[rt << 1], mx[rt << 1 | 1]));
num[rt] = mx[rt << 1] > mx[rt << 1 | 1] ? num[rt << 1] : num[rt << 1 | 1];
}
}
void build(int rt, int l, int r) {
if (l == r) {
scanf("%lld", &sum[rt]);
mx[rt] = sum[rt];
se[rt] = -1;
num[rt] = 1;
return;
}
build(lson);
build(rson);
pushup(rt);
}
void putTag(int rt, int x) {
if (x >= mx[rt]) return;
sum[rt] -= num[rt] * (mx[rt] - x);
mx[rt] = x;
}
void pushdown(int rt) {
putTag(rt << 1, mx[rt]);
putTag(rt << 1 | 1, mx[rt]);
}
void change(int L, int R, int rt, int l, int r, int x) {
if (x >= mx[rt]) return;
if (L <= l && R >= r && se[rt] < x) {
putTag(rt, x);
return;
}
pushdown(rt);
if (L <= (l + r) / 2) change(L, R, lson, x);
if (R > (l + r) / 2) change(L, R, rson, x);
pushup(rt);
}
int queryMax(int L, int R, int rt, int l, int r) {
if (L <= l && R >= r) {
return mx[rt];
}
pushdown(rt);
int ans = 0;
if (L <= (l + r) / 2) ans = queryMax(L, R, lson);
if (R > (l + r) / 2) ans = max(ans, queryMax(L, R, rson));
return ans;
}
ll querySum(int L, int R, int rt, int l, int r) {
if (L <= l && R >= r) {
return sum[rt];
}
pushdown(rt);
ll ans = 0;
if (L <= (l + r) / 2) ans += querySum(L, R, lson);
if (R > (l + r) / 2) ans += querySum(L, R, rson);
return ans;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
build(1, 1, n);
while (m--) {
int op, L, R, t;
scanf("%d%d%d", &op, &L, &R);
if (op == 0) {scanf("%d", &t); change(L, R, 1, 1, n, t);}
else if (op == 1) printf("%d\n", queryMax(L, R, 1, 1, n));
else printf("%lld\n", querySum(L, R, 1, 1, n));
}
}
return 0;
}