|
|
#include <iostream>
|
|
|
using namespace std;
|
|
|
typedef long long LL;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
const int N = 1e6 + 10;
|
|
|
|
|
|
#define ls u << 1
|
|
|
#define rs u << 1 | 1
|
|
|
|
|
|
//快读
|
|
|
int read() {
|
|
|
int x = 0, f = 1;
|
|
|
char ch = getchar();
|
|
|
while (ch < '0' || ch > '9') {
|
|
|
if (ch == '-') f = -1;
|
|
|
ch = getchar();
|
|
|
}
|
|
|
while (ch >= '0' && ch <= '9') {
|
|
|
x = (x << 3) + (x << 1) + (ch ^ 48);
|
|
|
ch = getchar();
|
|
|
}
|
|
|
return x * f;
|
|
|
}
|
|
|
|
|
|
struct Node {
|
|
|
int l, r, mx, se, cnt; // 区间最大值mx, 区间次大值se, 区间最大值个数cnt
|
|
|
LL sum; //区间和
|
|
|
} tr[N << 2];
|
|
|
|
|
|
//向上一级推送统计信息
|
|
|
void pushup(int u) {
|
|
|
tr[u].sum = tr[ls].sum + tr[rs].sum;
|
|
|
tr[u].mx = max(tr[ls].mx, tr[rs].mx);
|
|
|
|
|
|
if (tr[ls].mx == tr[rs].mx) { //左右儿子最大值样等
|
|
|
tr[u].cnt = tr[ls].cnt + tr[rs].cnt; //父亲的最大值个数=左儿子最大值个数+右儿子最大值个数
|
|
|
tr[u].se = max(tr[ls].se, tr[rs].se); //次大的，就需要讨论一下左右儿子谁的次大比较大
|
|
|
}
|
|
|
if (tr[ls].mx > tr[rs].mx) { //如果左儿子最大值大于右儿子最大值
|
|
|
tr[u].cnt = tr[ls].cnt; //记录左儿子最大值个数
|
|
|
tr[u].se = max(tr[ls].se, tr[rs].mx); //次大变成左儿子次大值，与右儿子最大值PK
|
|
|
}
|
|
|
if (tr[ls].mx < tr[rs].mx) {
|
|
|
tr[u].cnt = tr[rs].cnt;
|
|
|
tr[u].se = max(tr[rs].se, tr[ls].mx);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//构建线段树
|
|
|
void build(int u, int l, int r) {
|
|
|
// 每个都认真初始化,全部赋值一遍最稳妥
|
|
|
// 此题卡时间卡的比较严重，如果不用下面的方法，每次memset(tr,0,sizeof(tr));就会TLE
|
|
|
tr[u].l = l, tr[u].r = r, tr[u].mx = tr[u].cnt = tr[u].sum = 0;
|
|
|
tr[u].se = -INF; //初始时没有次大值,最小值是0，所以设置成-INF就肯定小于最小值了
|
|
|
|
|
|
if (l == r) {
|
|
|
tr[u].sum = tr[u].mx = read();
|
|
|
tr[u].cnt = 1;
|
|
|
return;
|
|
|
}
|
|
|
int mid = (l + r) >> 1;
|
|
|
build(ls, l, mid), build(rs, mid + 1, r);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
//将modify拆分成两个，独立出来
|
|
|
void update_min(int u, int v) {
|
|
|
if (tr[u].mx <= v) return; //最大值都没有k大，k就是无用的东西
|
|
|
tr[u].sum += ((LL)v - tr[u].mx) * tr[u].cnt; // 区间整体命中，并且比最大值小，能修改的只有最大值
|
|
|
tr[u].mx = v; // 最大值修改为k
|
|
|
}
|
|
|
|
|
|
//向下一级传递懒标记tag标记,此时的懒标记就是tr[u].mx也就是区间最大值
|
|
|
void pushdown(int u) {
|
|
|
update_min(ls, tr[u].mx), update_min(rs, tr[u].mx);
|
|
|
}
|
|
|
|
|
|
void modify_min(int u, int l, int r, int v) {
|
|
|
// ①与修改区间与当前区间无次，或，k>=tr[u].mx 时，没有修改的必要
|
|
|
if (r < tr[u].l || l > tr[u].r || v >= tr[u].mx) return;
|
|
|
|
|
|
// ②整个区间命中，不用再分裂，并且，tr[u].se<k<tr[u].mx ，update(u,k)将只改最大
|
|
|
if (l <= tr[u].l && tr[u].r <= r && tr[u].se < v) {
|
|
|
update_min(u, v);
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
//③ k <=tr[u].se 时，无法实现只对最大值的修改，只能继续分裂，直到区间可以被上面两种条件覆盖到
|
|
|
pushdown(u); //先下传lazy懒标记,防止有上次的累计懒标记没有处理，造成标记错乱或丢失
|
|
|
|
|
|
//递归左右儿子
|
|
|
modify_min(ls, l, r, v), modify_min(rs, l, r, v);
|
|
|
|
|
|
//叶子节点修改后，别忘了再上传统计信息,比如什么最大值个数，次大值是谁啥的，上面可都没管，但最终修改后要更新一次
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
//普通线段树的区间最大值
|
|
|
int query_max(int u, int l, int r) {
|
|
|
if (r < tr[u].l || l > tr[u].r) return -INF;
|
|
|
if (l <= tr[u].l && tr[u].r <= r) return tr[u].mx;
|
|
|
pushdown(u);
|
|
|
return max(query_max(ls, l, r), query_max(rs, l, r));
|
|
|
}
|
|
|
|
|
|
//普通线段树的区间和
|
|
|
LL query_sum(int u, int l, int r) {
|
|
|
if (r < tr[u].l || l > tr[u].r) return 0;
|
|
|
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum; //完全在查询区间内，直接返回tr[u].sum
|
|
|
|
|
|
pushdown(u);
|
|
|
return query_sum(ls, l, r) + query_sum(rs, l, r);
|
|
|
}
|
|
|
|
|
|
void solve() {
|
|
|
int n = read(), m = read();
|
|
|
//构建线段树
|
|
|
build(1, 1, n);
|
|
|
|
|
|
while (m--) {
|
|
|
int op = read(), l = read(), r = read();
|
|
|
|
|
|
if (op == 0) {
|
|
|
int v = read();
|
|
|
modify_min(1, l, r, v); //将区间[l,r]中a[i](i∈[l,r]),与x取min,最后，将整个区间修改为min(x,a[i])
|
|
|
}
|
|
|
if (op == 1) printf("%d\n", query_max(1, l, r)); //查询区间最大值
|
|
|
|
|
|
if (op == 2) printf("%lld\n", query_sum(1, l, r)); // 查询区间和
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//文件输入输出
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("HDU5306.in", "r", stdin);
|
|
|
#endif
|
|
|
int T = read();
|
|
|
for (int i = 1; i <= T; i++) solve(); //多组测试数据，提取solve函数，然后执行T次是一个好方法
|
|
|
return 0;
|
|
|
}
|
