吉如一线段树:区间最值和历史最值

区间最值和历史最值

问题一

给定一个长度为 $n$ 的数组 $a$ , 实现以下三种操作 :

0 l r x : 将 $arr[l\sim r]$ 范围的每个数 $v$ , 更新为 $\min (v,x)$

1 l r : 查询 ${\max }_{i=l}^{r}ar{r}_i$

2 l r : 查询 ${\sum }_{i=l}^{r}ar{r}_i$

吉如一线段树。

#include<bits/stdc++.h>
using namespace std;
#define int long long#define lc u << 1
#define rc u << 1 | 1int const N = 5e5 + 10;struct node{// mx : 最大值 ; cnt : mx 出现次数// se : 第二大// sum : 区间和int l, r, mx, cnt, se, sum;
}tr[N << 2];int a[N];void pushup(int u){tr[u].sum = tr[lc].sum + tr[rc].sum;tr[u].mx = max(tr[lc].mx, tr[rc].mx);if(tr[lc].mx == tr[rc].mx){tr[u].cnt = tr[lc].cnt + tr[rc].cnt;tr[u].se = max(tr[lc].se, tr[rc].se);}else if(tr[lc].mx > tr[rc].mx){tr[u].cnt = tr[lc].cnt;tr[u].se = max(tr[lc].se, tr[rc].mx);}else{tr[u].cnt = tr[rc].cnt;tr[u].se = max(tr[lc].mx, tr[rc].se);}
}void pushdown(int u){if(tr[lc].mx > tr[u].mx){ // 标记回收tr[lc].sum -= (tr[lc].mx - tr[u].mx) * tr[lc].cnt;tr[lc].mx = tr[u].mx;}if(tr[rc].mx > tr[u].mx){ // 标记回收tr[rc].sum -= (tr[rc].mx - tr[u].mx) * tr[rc].cnt;tr[rc].mx = tr[u].mx;}
}void build(int u, int l, int r){tr[u] = {l, r, a[l], 1, LLONG_MIN, a[l]};if(l == r) return ;int mid = l + r >> 1;build(lc, l, mid);build(rc, mid + 1, r);pushup(u);
}void setMin(int u, int l, int r, int x){if(x >= tr[u].mx) return ;if(l <= tr[u].l && r >= tr[u].r && x > tr[u].se){tr[u].sum -= (tr[u].mx - x) * tr[u].cnt;tr[u].mx = x;return ;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) setMin(lc, l, r, x);if(r > mid) setMin(rc, l, r, x);pushup(u);
}int askMax(int u, int l, int r){if(l <= tr[u].l && r >= tr[u].r){return tr[u].mx;}int mid = tr[u].l + tr[u].r >> 1;pushdown(u);int res = LLONG_MIN;if(l <= mid) res = max(res, askMax(lc, l, r));if(r > mid) res = max(res, askMax(rc, l, r));return res;
}int askSum(int u, int l, int r){if(l <= tr[u].l && r >= tr[u].r){return tr[u].sum;}int mid = tr[u].l + tr[u].r >> 1;pushdown(u);int sum = 0;if(l <= mid) sum += askSum(lc, l, r);if(r > mid) sum += askSum(rc, l, r);return sum;
}void solve(){int n, q;cin >> n >> q;for(int i = 1; i <= n; i ++){cin >> a[i];}build(1, 1, n);while(q --){int op, l, r, t;cin >> op >> l >> r;if(op == 0){cin >> t;setMin(1, l, r, t);}else if(op == 1){cout << askMax(1, l, r) << '\n';}else{cout << askSum(1, l, r) << '\n';}}
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); int T;cin >> T;while(T --){solve();}return 0;
}

问题二

题目背景

本题是线段树维护区间最值操作与区间历史最值的模板。

题目描述

给出一个长度为 $n$ 的数列 $A$，同时定义一个辅助数组 $B$，$B$ 开始与 $A$ 完全相同。接下来进行了 $m$ 次操作，操作有五种类型，按以下格式给出：

• 1 l r k：对于所有的 $i\in [l,r]$，将 $A_i$ 加上 $k$（$k$ 可以为负数）。
• 2 l r v：对于所有的 $i\in [l,r]$，将 $A_i$ 变成 $\min (A_i,v)$。
• 3 l r：求 ${\sum }_{i=l}^r{A}_i$。
• 4 l r：对于所有的 $i\in [l,r]$，求 $A_i$ 的最大值。
• 5 l r：对于所有的 $i\in [l,r]$，求 $B_i$ 的最大值。

在每一次操作后，我们都进行一次更新，让 $B_i\leftarrow \max (B_i,A_i)$。

输入格式

第一行包含两个正整数 $n,m$，分别表示数列 $A$ 的长度和操作次数。

第二行包含 $n$ 个整数 $A_1,A_2,\cdots ,A_n$，表示数列 $A$。

接下来 $m$ 行，每行行首有一个整数 $op$，表示操作类型；接下来两个或三个整数表示操作参数，格式见【题目描述】。

输出格式

对于 o p ∈ { 3 , 4 , 5 } op\in\{3,4,5\} op∈{3,4,5} 的操作，输出一行包含一个整数，表示这个询问的答案。

样例 #1

样例输入 #1

5 6
1 2 3 4 5
3 2 5
1 1 3 3
4 2 4
2 3 4 1
5 1 5
3 1 4

样例输出 #1

14
6
6
11

提示

样例说明 #1

操作次数	输入内容	操作	数列	输出结果
0			$1,2,3,4,5$
1	3 2 5	求出 $[2,5]$ 所有数的和	$1,2,3,4,5$	14
2	1 1 3 3	将 $[1,3]$ 内所有数加 $3$	$4,5,6,4,5$
3	4 2 4	求出 $[2,4]$ 所有数的最大值	$4,5,6,4,5$	6
4	2 3 4 1	将 $[3,4]$ 所有数与 $1$ 取最小值	$4,5,1,1,5$
5	5 1 5	求出 $[1,5]$ 所有位置历史最大值的最大值	$4,5,1,1,5$	6
6	3 1 4	求出 $[1,4]$ 所有数的和	$4,5,1,1,5$	11

数据规模与约定

• 对于测试点 $1,2$，满足 $n,m\le 5000$；
• 对于测试点 $3,4$，满足 o p ∈ { 1 , 2 , 3 , 4 } op\in\{1,2,3,4\} op∈{1,2,3,4}；
• 对于测试点 $5,6$，满足 o p ∈ { 1 , 3 , 4 , 5 } op\in\{1,3,4,5\} op∈{1,3,4,5}；
• 对于全部测试数据，保证 $1\le n,m\le 5\times 10^5$，$-5\times 10^8\le A_i\le 5\times 10^8$，$op\in [1,5]$，$1\le l\le r\le n$，$-2000\le k\le 2000$，$-5\times 10^8\le v\le 5\times 10^8$。

提示

本题输入量较大，请使用合理高效的读入方法。

#include<bits/stdc++.h>
using namespace std;
#define int long long#define lc u << 1
#define rc u << 1 | 1int const N = 5e5 + 10;struct node{// mx : 最大值 ; cnt : mx 出现次数// se : 第二大// sum : 区间和// mxhis : 历史最大值// add1, add2 : 区间最大值/非最大的懒标记// add3, add4 : 最大值懒标记历史最大值, 非最大值懒标记最历史大值int l, r, mx, cnt, se, sum, mxhis;int add1, add2, add3, add4;
}tr[N << 2];int a[N];void pushup(int u){tr[u].sum = tr[lc].sum + tr[rc].sum;tr[u].mx = max(tr[lc].mx, tr[rc].mx);tr[u].mxhis = max(tr[lc].mxhis, tr[rc].mxhis);if(tr[lc].mx == tr[rc].mx){tr[u].cnt = tr[lc].cnt + tr[rc].cnt;tr[u].se = max(tr[lc].se, tr[rc].se);}else if(tr[lc].mx > tr[rc].mx){tr[u].cnt = tr[lc].cnt;tr[u].se = max(tr[lc].se, tr[rc].mx);}else{tr[u].cnt = tr[rc].cnt;tr[u].se = max(tr[lc].mx, tr[rc].se);}
}void down(int u, int add1, int add2, int add3, int add4){tr[u].sum += add1 * tr[u].cnt + add2 * (tr[u].r - tr[u].l + 1 - tr[u].cnt);tr[u].mxhis = max(tr[u].mxhis, tr[u].mx + add3);tr[u].mx += add1;if(tr[u].se != LLONG_MIN) tr[u].se += add2;tr[u].add3 = max(tr[u].add3, tr[u].add1 + add3);tr[u].add4 = max(tr[u].add4, tr[u].add2 + add4);tr[u].add1 += add1;tr[u].add2 += add2;
}void pushdown(int u){int maxn = max(tr[lc].mx, tr[rc].mx);if(tr[lc].mx == maxn){down(lc, tr[u].add1, tr[u].add2, tr[u].add3, tr[u].add4);}else{down(lc, tr[u].add2, tr[u].add2, tr[u].add4, tr[u].add4);}if(tr[rc].mx == maxn){down(rc, tr[u].add1, tr[u].add2, tr[u].add3, tr[u].add4);}else{down(rc, tr[u].add2, tr[u].add2, tr[u].add4, tr[u].add4);}tr[u].add1 = tr[u].add2 = tr[u].add3 = tr[u].add4 = 0;
}void build(int u, int l, int r){tr[u] = {l, r, a[l], 1, LLONG_MIN, a[l], a[l], 0, 0, 0, 0};if(l == r) return ;int mid = l + r >> 1;build(lc, l, mid);build(rc, mid + 1, r);pushup(u);
}void segAdd(int u, int l, int r, int x){if(l <= tr[u].l && r >= tr[u].r){tr[u].sum += x * (tr[u].r - tr[u].l + 1);tr[u].mx += x;tr[u].mxhis = max(tr[u].mx, tr[u].mxhis);if(tr[u].se != LLONG_MIN) tr[u].se += x;tr[u].add1 += x, tr[u].add2 += x;tr[u].add3 = max(tr[u].add3, tr[u].add1);tr[u].add4 = max(tr[u].add4, tr[u].add2);return ;}int mid = tr[u].l + tr[u].r >> 1;pushdown(u);if(l <= mid) segAdd(lc, l, r, x);if(r > mid) segAdd(rc, l, r, x);pushup(u);
}void setMin(int u, int l, int r, int x){if(x >= tr[u].mx) return ;if(l <= tr[u].l && r >= tr[u].r && x > tr[u].se){int t = tr[u].mx - x;tr[u].sum -= t * tr[u].cnt;tr[u].mx = x;tr[u].add1 -= t;return ;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) setMin(lc, l, r, x);if(r > mid) setMin(rc, l, r, x);pushup(u);
}int askMax(int u, int l, int r){if(l <= tr[u].l && r >= tr[u].r){return tr[u].mx;}int mid = tr[u].l + tr[u].r >> 1;pushdown(u);int res = LLONG_MIN;if(l <= mid) res = max(res, askMax(lc, l, r));if(r > mid) res = max(res, askMax(rc, l, r));return res;
}int askMaxHis(int u, int l, int r){if(l <= tr[u].l && r >= tr[u].r){return tr[u].mxhis;}int mid = tr[u].l + tr[u].r >> 1;pushdown(u);int res = LLONG_MIN;if(l <= mid) res = max(res, askMaxHis(lc, l, r));if(r > mid) res = max(res, askMaxHis(rc, l, r));return res;
}int askSum(int u, int l, int r){if(l <= tr[u].l && r >= tr[u].r){return tr[u].sum;}int mid = tr[u].l + tr[u].r >> 1;pushdown(u);int sum = 0;if(l <= mid) sum += askSum(lc, l, r);if(r > mid) sum += askSum(rc, l, r);return sum;
}void solve(){int n, q;cin >> n >> q;for(int i = 1; i <= n; i ++){cin >> a[i];}build(1, 1, n);while(q --){int op, l, r, t;cin >> op >> l >> r;if(op == 1){cin >> t;segAdd(1, l, r, t);}else if(op == 2){cin >> t;setMin(1, l, r, t);}else if(op == 3){cout << askSum(1, l, r) << '\n';}else if(op == 4){cout << askMax(1, l, r) << '\n';}else{cout << askMaxHis(1, l, r) << '\n';}}
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); int T = 1;while(T --){solve();}return 0;
}