1 条题解

  • 1
    @ 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

琪露诺的完美算术教室 / 【模版】基础线段树

信息

ID
1004
难度
(无)
分类
线段树 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者