$Picks \; loves \; segment \; tree \; VIII$
存档。
查询区间和不知道写的对不对。
#include <iostream>
#include <cstring>
using namespace std;
using i64 = long long;
const int inf = 2e9;
const int N = 500010;
struct Tag {
int add, mx, mn;
void clear() {
add = mx = mn = 0;
}
};
Tag operator+ (Tag a, Tag b) {
a.mx = max(a.mx, a.add + b.mx);
a.mn = min(a.mn, a.add + b.mn);
a.add += b.add;
return a;
}
struct Max {
int val, se, his, cnt;
} tmpmx;
Max operator+ (Max a, Max b) {
if (a.val == b.val) {
a.se = max(a.se, b.se);
a.cnt = a.cnt + b.cnt;
} else if (a.val < b.val) {
a.cnt = b.cnt;
a.se = max(a.val, b.se);
} else {
a.se = max(a.se, b.val);
}
a.val = max(a.val, b.val);
a.his = max(a.his, b.his);
return a;
}
struct Min {
int val, se, his, cnt;
} tmpmn;
Min operator+ (Min a, Min b) {
if (a.val == b.val) {
a.se = min(a.se, b.se);
a.cnt = a.cnt + b.cnt;
} else if (a.val > b.val) {
a.se = min(a.val, b.se);
a.cnt = b.cnt;
} else {
a.se = min(a.se, b.val);
}
a.val = min(a.val, b.val);
a.his = min(a.his, b.his);
return a;
}
struct Node {
int l, r;
i64 sum;
Max mx;
Min mn;
Tag tmx, tmn, oth;
void cleartag() {
tmx.clear();
tmn.clear();
oth.clear();
}
} tr[N << 2];
int n, m;
int w[N];
#define ls (u << 1)
#define rs (u << 1 | 1)
void pushup(int u) {
tr[u].mx = tr[ls].mx + tr[rs].mx;
tr[u].mn = tr[ls].mn + tr[rs].mn;
tr[u].sum = tr[ls].sum + tr[rs].sum;
}
void build(int u, int l, int r) {
tr[u].l = l, tr[u].r = r;
if (l == r) {
tr[u].sum = w[l];
tr[u].mn = {w[l], inf, w[l], 1};
tr[u].mx = {w[l], -inf, w[l], 1};
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void pushmn(Node& u, Tag t) {
u.sum += 1ll * t.add * u.mn.cnt;
u.mn.his = min(u.mn.his, u.mn.val + t.mn);
if (tmpmn.val == tmpmx.se) u.mx.se += t.add;
u.mn.val += t.add;
u.tmn = u.tmn + t;
}
void pushmx(Node& u, Tag t) {
if (tmpmn.val != tmpmx.val) u.sum += 1ll * t.add * u.mx.cnt;
u.mx.his = max(u.mx.his, u.mx.val + t.mx);
if (tmpmn.se == tmpmx.val) u.mn.se += t.add;
u.mx.val += t.add;
u.tmx = u.tmx + t;
}
void pushoth(Node& u, Tag t) {
int cnt = u.r - u.l + 1;
if (tmpmn.val == tmpmx.val) cnt -= u.mx.cnt;
else cnt -= u.mx.cnt + u.mn.cnt;
u.sum += 1ll * t.add * cnt;
if (tmpmn.se != tmpmx.val && u.mn.se != inf) u.mn.se += t.add;
if (tmpmx.se != tmpmn.val && u.mx.se != -inf) u.mx.se += t.add;
u.oth = u.oth + t;
}
void pushall(Node& u, Tag t) {
u.sum += 1ll * t.add * (u.r - u.l + 1);
if (u.mx.se != -inf) u.mx.se += t.add;
if (u.mn.se != inf) u.mn.se += t.add;
u.mx.his = max(u.mx.his, u.mx.val += t.add);
u.mn.his = min(u.mn.his, u.mn.val += t.add);
u.tmn = u.tmn + t;
u.tmx = u.tmx + t;
u.oth = u.oth + t;
}
void pushdown(int x) {
Node &u = tr[x], &l = tr[x << 1], &r = tr[x << 1 | 1];
int mn = min(l.mn.val, r.mn.val);
int mx = max(l.mx.val, r.mx.val);
tmpmn = l.mn, tmpmx = l.mx;
if (l.mn.val == mn) pushmn(l, u.tmn);
else if (l.mn.val == mx) pushmn(l, u.tmx);
else pushmn(l, u.oth);
if (l.mx.val == mx) pushmx(l, u.tmx);
else if (l.mx.val == mn) pushmx(l, u.tmn);
else pushmx(l, u.oth);
pushoth(l, u.oth);
tmpmn = r.mn, tmpmx = r.mx;
if (r.mn.val == mn) pushmn(r, u.tmn);
else if (r.mn.val == mx) pushmn(r, u.tmx);
else pushmn(r, u.oth);
if (r.mx.val == mx) pushmx(r, u.tmx);
else if (r.mx.val == mn) pushmx(r, u.tmn);
else pushmx(r, u.oth);
pushoth(r, u.oth);
u.cleartag();
}
void cmax(int u, int l, int r, int v) {
if (tr[u].mn.val >= v) return;
if (tr[u].l >= l && tr[u].r <= r && tr[u].mn.se > v) {
v -= tr[u].mn.val;
tmpmx = tr[u].mx, tmpmn = tr[u].mn;
if (tr[u].mx.val == tr[u].mn.val) pushmx(tr[u], {v, v, v});
return pushmn(tr[u], {v, v, v});
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) cmax(u << 1, l, r, v);
if (r > mid) cmax(u << 1 | 1, l, r, v);
pushup(u);
}
void cmin(int u, int l, int r, int v) {
if (tr[u].mx.val <= v) return;
if (tr[u].l >= l && tr[u].r <= r && tr[u].mx.se < v) {
v -= tr[u].mx.val;
tmpmx = tr[u].mx, tmpmn = tr[u].mn;
if (tr[u].mx.val == tr[u].mn.val) pushmn(tr[u], {v, v, v});
return pushmx(tr[u], {v, v, v});
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) cmin(u << 1, l, r, v);
if (r > mid) cmin(u << 1 | 1, l, r, v);
pushup(u);
}
void add(int u, int l, int r, int v) {
if (tr[u].l >= l && tr[u].r <= r)
return pushall(tr[u], {v, v, v});
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) add(u << 1, l, r, v);
if (r > mid) add(u << 1 | 1, l, r, v);
pushup(u);
}
int query_mn(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].mn.val;
int mid = tr[u].l + tr[u].r >> 1, res = inf;
pushdown(u);
if (l <= mid) res = min(res, query_mn(u << 1, l, r));
if (r > mid) res = min(res, query_mn(u << 1 | 1, l, r));
return res;
}
int query_hmn(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].mn.his;
int mid = tr[u].l + tr[u].r >> 1, res = inf;
pushdown(u);
if (l <= mid) res = min(res, query_hmn(u << 1, l, r));
if (r > mid) res = min(res, query_hmn(u << 1 | 1, l, r));
return res;
}
int query_hmx(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].mx.his;
int mid = tr[u].l + tr[u].r >> 1, res = -inf;
pushdown(u);
if (l <= mid) res = max(res, query_hmx(u << 1, l, r));
if (r > mid) res = max(res, query_hmx(u << 1 | 1, l, r));
return res;
}
i64 query_sum(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
int mid = tr[u].l + tr[u].r >> 1;
i64 res = 0;
pushdown(u);
if (l <= mid) res += query_sum(u << 1, l, r);
if (r > mid) res += query_sum(u << 1 | 1, l, r);
return res;
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
build(1, 1, n);
while (m--) {
int op, l, r, x;
cin >> op >> l >> r;
if (op == 1) {
cin >> x;
add(1, l, r, x);
}
if (op == 2) {
cin >> x;
cmax(1, l, r, x);
}
if (op == 3) {
cout << query_mn(1, l, r) << '\n';
}
if (op == 4) {
cout << query_hmn(1, l, r) << '\n';
}
if (op == 5) {
cin >> x;
cmin(1, l, r, x);
}
if (op == 6) {
cout << query_hmx(1, l, r) << '\n';
}
if (op == 7) {
cout << query_sum(1, l, r) << '\n';
}
}
return 0;
}
爹,你好帅
jls是我的叠