Description
给定 a = ( a 1 , a 2 , ⋯ , a n ) a=(a_1,a_2,\cdots,a_n) a=(a1,a2,⋯,an)，有 m m m 个操作，分以下六种：
- add ( l , r , k ) \operatorname{add}(l,r,k) add(l,r,k)：对每个 i ∈ [ l , r ] i \in[l,r] i∈[l,r] 执行 a i ← a i + k a_i \leftarrow a_i+k ai←ai+k.
- chmax ( l , r , v ) \operatorname{chmax}(l,r,v) chmax(l,r,v)：对每个 i ∈ [ l , r ] i \in[l,r] i∈[l,r] 执行 a i ← max ( a i , k ) a_i \leftarrow \max(a_i,k) ai←max(ai,k).
- chmin ( l , r , v ) \operatorname{chmin}(l,r,v) chmin(l,r,v)：对每个 i ∈ [ l , r ] i \in[l,r] i∈[l,r] 执行 a i ← min ( a i , k ) a_i \leftarrow \min(a_i,k) ai←min(ai,k).
- qsum ( l , r ) \operatorname{qsum}(l,r) qsum(l,r)：求 ∑ i = l r a i \sum\limits_{i=l}^r a_i i=l∑rai.
- qmax ( l , r ) \operatorname{qmax}(l,r) qmax(l,r)：求 max i = l r a i \max\limits_{i=l}^r a_i i=lmaxrai.
- qmin ( l , r ) \operatorname{qmin}(l,r) qmin(l,r)：求 min i = l r a i \min\limits_{i=l}^r a_i i=lminrai.
Limitations
1
≤
n
,
m
≤
5
×
1
0
5
1 \le n,m \le 5\times 10^5
1≤n,m≤5×105
∣
a
i
∣
,
∣
v
∣
≤
1
0
8
|a_i|,|v| \le 10^8
∣ai∣,∣v∣≤108
∣
k
∣
≤
1000
|k| \le 1000
∣k∣≤1000
2
s
,
512
MB
2\text{s},512\text{MB}
2s,512MB
Solution
显然的吉司机线段树.
节点上维护最大（小）值，次大（小）值，最大（小）值的出现次数，以及三种修改对应的三个标记.
考虑修改：
- add \operatorname{add} add 就是普通线段树.
- chmax \operatorname{chmax} chmax 时，如果当前节点 min ≤ v a l \textit{min}\le val min≤val，直接返回，否则若 secmin > v a l \textit{secmin}>val secmin>val 且节点在目标范围内，直接打上 chmax \textit{chmax} chmax 标记.
- chmin \operatorname{chmin} chmin 同理.
其他的就是板子，势能分析可得时间复杂度
O
(
m
log
2
n
)
O(m\log^2 n)
O(mlog2n).
有一些注意点：
- 开
long long. - 标记的幺元 e = ( 0 , − ∞ , ∞ ) e=(0,-\infty,\infty) e=(0,−∞,∞).
- 先传 add \textit{add} add 标记，再传另外两个.
apply时，若最大（小）值和次小（大）值相等，需要一起更新.
Code
7.21
KB
,
12.09
s
,
80.71
MB
(in
total,
C++
20
with
O2)
7.21\text{KB},12.09\text{s},80.71\text{MB}\;\texttt{(in total, C++ 20 with O2)}
7.21KB,12.09s,80.71MB(in total, C++ 20 with O2)
重构了
// Problem: P10639 BZOJ4695 最佳女选手
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10639
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;
template<class T>
bool chmax(T &a, const T &b){
if(a < b){ a = b; return true; }
return false;
}
template<class T>
bool chmin(T &a, const T &b){
if(a > b){ a = b; return true; }
return false;
}
constexpr i64 inf = 3e18;
namespace seg_tree {
struct Node {
int l, r, cmax, cmin;
i64 max, max2, min, min2;
i64 tag, tmin, tmax, sum;
};
inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }
struct SegTree {
vector<Node> tr;
inline SegTree() {}
inline SegTree(const vector<i64>& a) {
const int n = a.size();
tr.resize(n << 1);
build(0, 0, n - 1, a);
}
inline void pushup(int u, int mid) {
tr[u].sum = tr[ls(mid)].sum + tr[rs(mid)].sum;
if (tr[ls(mid)].max == tr[rs(mid)].max) {
tr[u].max = tr[ls(mid)].max;
tr[u].cmax = tr[ls(mid)].cmax + tr[rs(mid)].cmax;
tr[u].max2 = max(tr[ls(mid)].max2, tr[rs(mid)].max2);
}
else if (tr[ls(mid)].max > tr[rs(mid)].max) {
tr[u].max = tr[ls(mid)].max;
tr[u].cmax = tr[ls(mid)].cmax;
tr[u].max2 = max(tr[ls(mid)].max2, tr[rs(mid)].max);
}
else {
tr[u].max = tr[rs(mid)].max;
tr[u].cmax = tr[rs(mid)].cmax;
tr[u].max2 = max(tr[ls(mid)].max, tr[rs(mid)].max2);
}
if (tr[ls(mid)].min == tr[rs(mid)].min) {
tr[u].min = tr[ls(mid)].min;
tr[u].cmin = tr[ls(mid)].cmin + tr[rs(mid)].cmin;
tr[u].min2 = min(tr[ls(mid)].min2, tr[rs(mid)].min2);
}
else if (tr[ls(mid)].min < tr[rs(mid)].min) {
tr[u].min = tr[ls(mid)].min;
tr[u].cmin = tr[ls(mid)].cmin;
tr[u].min2 = min(tr[ls(mid)].min2, tr[rs(mid)].min);
}
else {
tr[u].min = tr[rs(mid)].min;
tr[u].cmin = tr[rs(mid)].cmin;
tr[u].min2 = min(tr[ls(mid)].min, tr[rs(mid)].min2);
}
}
inline void build(int u, int l, int r, const vector<i64>& a) {
tr[u].l = l;
tr[u].r = r;
tr[u].tmin = inf;
tr[u].tmax = -inf;
if (l == r) {
tr[u].sum = tr[u].max = tr[u].min = a[l];
tr[u].max2 = -inf;
tr[u].min2 = inf;
tr[u].cmax = tr[u].cmin = 1;
return;
}
const int mid = (l + r) >> 1;
build(ls(mid), l, mid, a);
build(rs(mid), mid + 1, r, a);
pushup(u, mid);
}
inline void apply(int u, i64 tag, i64 tmax, i64 tmin) {
tr[u].sum += tag * (tr[u].r - tr[u].l + 1);
tr[u].max += tag;
tr[u].min += tag;
if (tr[u].max2 != -inf) tr[u].max2 += tag;
if (tr[u].min2 != inf) tr[u].min2 += tag;
if (tr[u].tmax != -inf) tr[u].tmax += tag;
if (tr[u].tmin != inf) tr[u].tmin += tag;
tr[u].tag += tag;
if (tr[u].min < tmax) {
tr[u].sum += (tmax - tr[u].min) * tr[u].cmin;
if (tr[u].max2 == tr[u].min) tr[u].max2 = tmax;
if (tr[u].max == tr[u].min) tr[u].max = tmax;
tr[u].tmin = max(tr[u].tmin, tmax);
tr[u].min = tmax;
tr[u].tmax = tmax;
}
if (tr[u].max > tmin) {
tr[u].sum += (tmin - tr[u].max) * tr[u].cmax;
if (tr[u].min2 == tr[u].max) tr[u].min2 = tmin;
if (tr[u].min == tr[u].max) tr[u].min = tmin;
tr[u].tmax = min(tr[u].tmax, tmin);
tr[u].max = tmin;
tr[u].tmin = tmin;
}
}
inline void pushdown(int u, int mid) {
apply(ls(mid), tr[u].tag, tr[u].tmax, tr[u].tmin);
apply(rs(mid), tr[u].tag, tr[u].tmax, tr[u].tmin);
tr[u].tag = 0;
tr[u].tmax = -inf;
tr[u].tmin = inf;
}
inline void add(int u, int l, int r, i64 val) {
if (l <= tr[u].l && tr[u].r <= r) return apply(u, val, -inf, inf);
const int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u, mid);
if (l <= mid) add(ls(mid), l, r, val);
if (r > mid) add(rs(mid), l, r, val);
pushup(u, mid);
}
inline void chmin(int u, int l, int r, i64 val) {
if (tr[u].max <= val) return;
if (l <= tr[u].l && tr[u].r <= r && tr[u].max2 < val) return apply(u, 0, -inf, val);
const int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u, mid);
if (l <= mid) chmin(ls(mid), l, r, val);
if (r > mid) chmin(rs(mid), l, r, val);
pushup(u, mid);
}
inline void chmax(int u, int l, int r, i64 val) {
if (tr[u].min >= val) return;
if (l <= tr[u].l && tr[u].r <= r && tr[u].min2 > val) return apply(u, 0, val, inf);
const int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u, mid);
if (l <= mid) chmax(ls(mid), l, r, val);
if (r > mid) chmax(rs(mid), l, r, val);
pushup(u, mid);
}
inline i64 qsum(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
const int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u, mid);
if (r <= mid) return qsum(ls(mid), l, r);
else if (l > mid) return qsum(rs(mid), l, r);
else return qsum(ls(mid), l, r) + qsum(rs(mid), l, r);
}
inline i64 qmin(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].min;
const int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u, mid);
if (r <= mid) return qmin(ls(mid), l, r);
else if (l > mid) return qmin(rs(mid), l, r);
else return min(qmin(ls(mid), l, r), qmin(rs(mid), l, r));
}
inline i64 qmax(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].max;
const int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u, mid);
if (r <= mid) return qmax(ls(mid), l, r);
else if (l > mid) return qmax(rs(mid), l, r);
else return max(qmax(ls(mid), l, r), qmax(rs(mid), l, r));
}
inline void range_add(int l, int r, i64 x) { add(0, l, r, x); }
inline void range_chmin(int l, int r, i64 x) { chmin(0, l, r, x); }
inline void range_chmax(int l, int r, i64 x) { chmax(0, l, r, x); }
inline i64 range_sum(int l, int r) { return qsum(0, l, r); }
inline i64 range_min(int l, int r) { return qmin(0, l, r); }
inline i64 range_max(int l, int r) { return qmax(0, l, r); }
};
}
using seg_tree::SegTree;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n; scanf("%d", &n);
vector<i64> a(n);
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
int m; scanf("%d", &m);
SegTree sgt(a);
for (int i = 0, op, l, r, v; i < m; i++) {
scanf("%d %d %d", &op, &l, &r), l--, r--;
if (op == 1) {
scanf("%d", &v);
sgt.range_add(l, r, v);
}
if (op == 2) {
scanf("%d", &v);
sgt.range_chmax(l, r, v);
}
if (op == 3) {
scanf("%d", &v);
sgt.range_chmin(l, r, v);
}
if (op == 4) printf("%lld\n", sgt.range_sum(l, r));
if (op == 5) printf("%lld\n", sgt.range_max(l, r));
if (op == 6) printf("%lld\n", sgt.range_min(l, r));
}
return 0;
}
扫一扫
2094
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
