1 条题解
-
1チルノ (9Cirno) LV 7 MOD Baka tayz @ 2024-11-02 14:18:26
本题就是一个简单的线段树模版,我们只需要维护一下区间最大值,区间最小值和区间和即可。
std食用警告:为了偷懒,std中的query函数使用了相当多的三目运算符,使代码十分丑陋。
#include <iostream> using namespace std; typedef long long ll; const int N = 100010; const ll inf = 0x3f3f3f3f3f3f3f3f; ll n, m; ll a[N]; struct segment_tree { ll l, r; ll sum, maxn, minn; ll laz; segment_tree *ls, *rs; void push_up() { sum = ls->sum + rs->sum; maxn = max(ls->maxn, rs->maxn); minn = min(ls->minn, rs->minn); } void push_down() { if (laz) { ls->laz += laz; rs->laz += laz; ls->sum += (ls->r - ls->l + 1) * laz; rs->sum += (rs->r - rs->l + 1) * laz; ls->maxn += laz; rs->maxn += laz; ls->minn += laz; rs->minn += laz; } } void update(ll L, ll R, ll k) { if (L <= l && R >= r) { laz += k; sum += (r - l + 1) * k; maxn += k; minn += k; return; } push_down(); if (L <= ls->r) ls->update(L, R, k); if (R >= rs->l) rs->update(L, R, k); push_up(); } ll query(ll L, ll R, ll op) { if (L <= l && R >= r) return (op != 4 ? (op == 1 ? maxn : minn) : sum); push_down(); ll res = (op == 1 || op == 4 ? 0 : inf); if (L <= ls->r) (op == 4 ? res += ls->query(L, R, op) : res = (op == 1 ? max(res, ls->query(L, R, op)) : min(res, ls->query(L, R, op)))); if (R >= rs->l) (op == 4 ? res += rs->query(L, R, op) : res = (op == 1 ? max(res, rs->query(L, R, op)) : min(res, rs->query(L, R, op)))); return res; } } tree[N << 1], *pos = tree; segment_tree *build(ll l, ll r) { auto tmp = pos++; tmp->l = l, tmp->r = r; tmp->minn = inf; if (l != r) { ll mid = (l + r) >> 1; tmp->ls = build(l, mid); tmp->rs = build(mid + 1, r); tmp->push_up(); } else tmp->sum = tmp->maxn = tmp->minn = a[l]; return tmp; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; auto rt = build(1, n); while (m--) { ll op, l, r; cin >> op >> l >> r; if (op == 1 || op == 2) cout << rt->query(l, r, op) << '\n'; else if (op == 3) { ll k = rt->query(l, r, 1) - rt->query(l, r, 2); rt->update(l, r, k); } else cout << rt->query(l, r, op) / (r - l + 1) << '\n'; } return 0; }
- 1