Description
There is a sequence a of length n. We use ai to denote the i-th element in this sequence. You should do the following three types of operations to this sequence.
0 x y t: For every x≤i≤y, we use min(ai,t) to replace the original ai’s value.
1 x y: Print the maximum value of ai that x≤i≤y.
2 x y: Print the sum of ai that x≤i≤y
Input
The first line of the input is a single integer T, indicating the number of testcases.
The first line contains two integers n and m denoting the length of the sequence and the number of operations.
The second line contains n separated integers a1,…,an (?1≤i≤n,0≤ai<231).
Each of the following m lines represents one operation (1≤x≤y≤n,0≤t<231).
It is guaranteed that T=100, ∑n≤1000000, ∑m≤1000000
Output
For every operation of type 1 or 2, print one line containing the answer to the corresponding query.
Sample Input
1
5 5
1 2 3 4 5
1 1 5
2 1 5
0 3 5 3
1 1 5
2 1 5
Sample Output
5
15
3
12
Solution
题目：
三种操作
0 l r t: 使这个区间的每个值变成min(t,a[i])。
1 l r: 输出区间最大值
2 l r: 输出区间和
(1 <= n,m <= 1e6, 0 <= ai,t <= 2^31)
分析：
如果直接用线段树进行区间更新的话，会超时，这个时候就需要进行优化
维护 3 个值，区间最大值，区间严格次大值，区间最大值的个数。然后我们每次做0操作的时候，就会有3种情况。
- t >= 区间最大值, 这时每个值都不用修改，直接返回。
- 区间次大值 < t < 区间最大值，此时只有最大值会变，又已经求得了最大值的个数，所以我们可以直接更新这段的sum和max。
- 其他情况。无法直接对当前情况修改，所以继续搜两个儿子，直到搜到前两种情况为止。
把区间的最大值看做是这个区间的标记，因为每次更新的时候只会更新到（区间次大值 < t < 区间最大值）的情况，然后会修改sum和max，所以以后一旦进入这个区间的子树，必须先更新这个子树的max和sum。于是就有了pushdown()的写法，它就是负责把当前区间的sum和mx信息传给子树。
扩展：
bzoj 4355: Play with sequence
题目大意：维护一个长度为N的序列a，现在有三种操作：
1）给出参数U,V,C，将a[U],a[U+1],…,a[V-1],a[V]都赋值为C。
2）给出参数U,V,C，对于区间[U,V]里的每个数i，将a[i]赋值为max(a[i]+C,0)。
3）给出参数U,V，输出a[U],a[U+1],…,a[V-1],a[V]里值为0的数字个数。
代码：
#include<bits/stdc++.h>
using namespace std;
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*2]+sum[rt*2+1];
mx[rt]=max(mx[rt*2],mx[rt*2+1]);
if(mx[rt*2]==mx[2*rt+1]){
se[rt]=max(se[rt*2],se[rt*2+1]);
num[rt]=num[rt*2]+num[rt*2+1];
}
else{
se[rt] = max(se[rt*2],se[rt*2+1]);
se[rt] = max(se[rt],min(mx[rt*2], mx[rt*2+1]));
num[rt] = mx[rt*2] > mx[rt*2+1] ? num[rt*2] : num[rt*2+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(rt*2,l,(l+r)/2);
build(rt*2+1,(l+r)/2+1,r);
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*2,mx[rt]);
putTag(rt*2+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,rt*2,l,(l+r)/2, x);
if (R > (l + r) / 2) change(L, R,rt*2+1,(l+r)/2+1,r, 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,rt*2,l,(l+r)/2);
if (R>(l+r)/2) ans = max(ans, queryMax(L,R,rt*2+1,(l+r)/2+1,r));
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,rt*2,l,(l+r)/2);
if (R > (l + r) / 2) ans += querySum(L, R,rt*2+1,(l+r)/2+1,r);
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;
}