html5网站 欣赏,苍南县网站集约化建设,展览公司设计费,国家级示范校建设专题网站区间最值和历史最值
问题一 给定一个长度为 n n n 的数组 a a a , 实现以下三种操作 : 0 l r x : 将 a r r [ l ∼ r ] arr[l\sim r] arr[l∼r] 范围的每个数 v v v , 更新为 min ( v , x ) \min (v, x) min(v,x) 1 l r : 查询 max i l r a r r i \max_{il}^r ar…区间最值和历史最值
问题一 给定一个长度为 n n n 的数组 a a a , 实现以下三种操作 : 0 l r x : 将 a r r [ l ∼ r ] arr[l\sim r] arr[l∼r] 范围的每个数 v v v , 更新为 min ( v , x ) \min (v, x) min(v,x) 1 l r : 查询 max i l r a r r i \max_{il}^r arr_i maxilrarri 2 l r : 查询 ∑ i l r a r r i \sum_{il}^rarr_i ∑ilrarri 吉如一线段树。
#includebits/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 n n 的数列 A A A同时定义一个辅助数组 B B B B B B 开始与 A A A 完全相同。接下来进行了 m m m 次操作操作有五种类型按以下格式给出
1 l r k对于所有的 i ∈ [ l , r ] i\in[l,r] i∈[l,r]将 A i A_i Ai 加上 k k k k k k 可以为负数。2 l r v对于所有的 i ∈ [ l , r ] i\in[l,r] i∈[l,r]将 A i A_i Ai 变成 min ( A i , v ) \min(A_i,v) min(Ai,v)。3 l r求 ∑ i l r A i \sum_{il}^{r}A_i ∑ilrAi。4 l r对于所有的 i ∈ [ l , r ] i\in[l,r] i∈[l,r]求 A i A_i Ai 的最大值。5 l r对于所有的 i ∈ [ l , r ] i\in[l,r] i∈[l,r]求 B i B_i Bi 的最大值。
在每一次操作后我们都进行一次更新让 B i ← max ( B i , A i ) B_i\gets\max(B_i,A_i) Bi←max(Bi,Ai)。
输入格式
第一行包含两个正整数 n , m n,m n,m分别表示数列 A A A 的长度和操作次数。
第二行包含 n n n 个整数 A 1 , A 2 , ⋯ , A n A_1,A_2,\cdots,A_n A1,A2,⋯,An表示数列 A A A。
接下来 m m m 行每行行首有一个整数 o p op 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,2,3,4,5 1,2,3,4,513 2 5求出 [ 2 , 5 ] [2,5] [2,5] 所有数的和 1 , 2 , 3 , 4 , 5 1,2,3,4,5 1,2,3,4,51421 1 3 3将 [ 1 , 3 ] [1,3] [1,3] 内所有数加 3 3 3 4 , 5 , 6 , 4 , 5 4,5,6,4,5 4,5,6,4,534 2 4求出 [ 2 , 4 ] [2,4] [2,4] 所有数的最大值 4 , 5 , 6 , 4 , 5 4,5,6,4,5 4,5,6,4,5642 3 4 1将 [ 3 , 4 ] [3,4] [3,4] 所有数与 1 1 1 取最小值 4 , 5 , 1 , 1 , 5 4,5,1,1,5 4,5,1,1,555 1 5求出 [ 1 , 5 ] [1,5] [1,5] 所有位置历史最大值的最大值 4 , 5 , 1 , 1 , 5 4,5,1,1,5 4,5,1,1,5663 1 4求出 [ 1 , 4 ] [1,4] [1,4] 所有数的和 4 , 5 , 1 , 1 , 5 4,5,1,1,5 4,5,1,1,511
数据规模与约定
对于测试点 1 , 2 1,2 1,2满足 n , m ≤ 5000 n,m\leq 5000 n,m≤5000对于测试点 3 , 4 3,4 3,4满足 o p ∈ { 1 , 2 , 3 , 4 } op\in\{1,2,3,4\} op∈{1,2,3,4}对于测试点 5 , 6 5,6 5,6满足 o p ∈ { 1 , 3 , 4 , 5 } op\in\{1,3,4,5\} op∈{1,3,4,5}对于全部测试数据保证 1 ≤ n , m ≤ 5 × 1 0 5 1\leq n,m\leq 5\times 10^5 1≤n,m≤5×105 − 5 × 1 0 8 ≤ A i ≤ 5 × 1 0 8 -5\times10^8\leq A_i\leq 5\times10^8 −5×108≤Ai≤5×108 o p ∈ [ 1 , 5 ] op\in[1,5] op∈[1,5] 1 ≤ l ≤ r ≤ n 1 \leq l\leq r \leq n 1≤l≤r≤n − 2000 ≤ k ≤ 2000 -2000\leq k\leq 2000 −2000≤k≤2000 − 5 × 1 0 8 ≤ v ≤ 5 × 1 0 8 -5\times10^8\leq v\leq 5\times10^8 −5×108≤v≤5×108。
提示
本题输入量较大请使用合理高效的读入方法。
#includebits/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;
}
