Segment Tree Beats
stripe_python · · 算法·理论
Segment Tree Beats 用于解决区间 chkmax / chkmin 的问题。
segbeats 的核心是一个剪枝:线段树节点上维护三个信息
- 若
c \ge \text{mx} ,则操作无意义,终止递归; - 若
c \in (\text{mx2},\text{mx}) ,则仅有最大值被修改,令区间和加上(c-\text{mx}) \times \text{mxcnt} ,令\text{mx} \gets c 并打上标记。 - 若
c \le \text{mx2} ,递归到子树中修改。
使用势能分析法可以证明上述算法的复杂度上限为 2log。下限的构造式证明。
BZOJ4695 最假女选手
板子题。考虑维护
修改要维护加标记、chkmax 标记和 chkmin 标记。对于标记优先级,我们认为加标记优先级最高,最值操作标记同级。注意在下传标记时特判区间长度较小的 corner case。
:::::info[代码]
const int N = 5e5 + 5;
int n, q, a[N];
struct segbeats {
static const int inf = 2e9;
#define ls (rt << 1)
#define rs (rt << 1 | 1)
struct node {
int mx, mx2, mxcnt, mn, mn2, mncnt; i64 sum;
node() = default;
explicit node(int v) : mx(v), mx2(-inf), mxcnt(1), mn(v), mn2(inf), mncnt(1), sum(v) {}
friend node operator+ (const node& a, const node& b) {
node c; c.sum = a.sum + b.sum;
if (a.mx == b.mx) c.mx = a.mx, c.mx2 = max(a.mx2, b.mx2), c.mxcnt = a.mxcnt + b.mxcnt;
else if (a.mx > b.mx) c.mx = a.mx, c.mx2 = max(a.mx2, b.mx), c.mxcnt = a.mxcnt;
else c.mx = b.mx, c.mx2 = max(b.mx2, a.mx), c.mxcnt = b.mxcnt;
if (a.mn == b.mn) c.mn = a.mn, c.mn2 = min(a.mn2, b.mn2), c.mncnt = a.mncnt + b.mncnt;
else if (a.mn < b.mn) c.mn = a.mn, c.mn2 = min(a.mn2, b.mn), c.mncnt = a.mncnt;
else c.mn = b.mn, c.mn2 = min(b.mn2, a.mn), c.mncnt = b.mncnt;
return c;
}
};
node val[4*N];
int cmx[4*N], cmn[4*N], add[4*N];
void pushup(int rt) {val[rt] = val[ls] + val[rs];}
void apply_add(int rt, int c, int len) {
val[rt].sum += 1LL * c * len, val[rt].mx += c, val[rt].mn += c;
if (val[rt].mx2 != -inf) val[rt].mx2 += c;
if (val[rt].mn2 != inf) val[rt].mn2 += c;
if (cmx[rt] != -inf) cmx[rt] += c;
if (cmn[rt] != inf) cmn[rt] += c;
add[rt] += c;
}
void apply_max(int rt, int c) {
if (val[rt].mn >= c) return;
val[rt].sum += 1LL * (c - val[rt].mn) * val[rt].mncnt;
if (val[rt].mx2 == val[rt].mn) val[rt].mx2 = c;
if (val[rt].mx == val[rt].mn) val[rt].mx = c;
chkmax(cmn[rt], c), val[rt].mn = c, cmx[rt] = c;
}
void apply_min(int rt, int c) {
if (val[rt].mx <= c) return;
val[rt].sum -= 1LL * (val[rt].mx - c) * val[rt].mxcnt;
if (val[rt].mn2 == val[rt].mx) val[rt].mn2 = c;
if (val[rt].mn == val[rt].mx) val[rt].mn = c;
chkmin(cmx[rt], c), val[rt].mx = c, cmn[rt] = c;
}
void pushdown(int rt, int ln, int rn) {
if (add[rt]) apply_add(ls, add[rt], ln), apply_add(rs, add[rt], rn), add[rt] = 0;
if (cmx[rt] != -inf) apply_max(ls, cmx[rt]), apply_max(rs, cmx[rt]), cmx[rt] = -inf;
if (cmn[rt] != inf) apply_min(ls, cmn[rt]), apply_min(rs, cmn[rt]), cmn[rt] = inf;
}
void build(int l = 1, int r = n, int rt = 1) {
add[rt] = 0, cmx[rt] = -inf, cmn[rt] = inf;
if (l == r) return val[rt] = node(a[l]), void();
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs), pushup(rt);
}
void update_add(int tl, int tr, int c, int l = 1, int r = n, int rt = 1) {
if (tl <= l && r <= tr) return apply_add(rt, c, r-l+1), void();
int mid = (l + r) >> 1; pushdown(rt, mid-l+1, r-mid);
if (tl <= mid) update_add(tl, tr, c, l, mid, ls);
if (tr > mid) update_add(tl, tr, c, mid + 1, r, rs);
pushup(rt);
}
void update_max(int tl, int tr, int c, int l = 1, int r = n, int rt = 1) {
if (c <= val[rt].mn) return;
if (tl <= l && r <= tr && c < val[rt].mn2) return apply_max(rt, c), void();
int mid = (l + r) >> 1; pushdown(rt, mid-l+1, r-mid);
if (tl <= mid) update_max(tl, tr, c, l, mid, ls);
if (tr > mid) update_max(tl, tr, c, mid + 1, r, rs);
pushup(rt);
}
void update_min(int tl, int tr, int c, int l = 1, int r = n, int rt = 1) {
if (c >= val[rt].mx) return;
if (tl <= l && r <= tr && c > val[rt].mx2) return apply_min(rt, c), void();
int mid = (l + r) >> 1; pushdown(rt, mid-l+1, r-mid);
if (tl <= mid) update_min(tl, tr, c, l, mid, ls);
if (tr > mid) update_min(tl, tr, c, mid + 1, r, rs);
pushup(rt);
}
node ask(int tl, int tr, int l = 1, int r = n, int rt = 1) {
if (tl <= l && r <= tr) return val[rt];
int mid = (l + r) >> 1; pushdown(rt, mid-l+1, r-mid);
if (tl <= mid && mid < tr) return ask(tl, tr, l, mid, ls) + ask(tl, tr, mid + 1, r, rs);
return tl <= mid ? ask(tl, tr, l, mid, ls) : ask(tl, tr, mid + 1, r, rs);
}
} T;
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
T.build(); cin >> q;
for (int op, l, r, x; q--; ) {
cin >> op >> l >> r;
if (op == 1) cin >> x, T.update_add(l, r, x);
if (op == 2) cin >> x, T.update_max(l, r, x);
if (op == 3) cin >> x, T.update_min(l, r, x);
if (op == 4) cout << T.ask(l, r).sum << '\n';
if (op == 5) cout << T.ask(l, r).mx << '\n';
if (op == 6) cout << T.ask(l, r).mn << '\n';
}
}
:::::