verify/Datastructure_point_add_rec_sum.test.cpp

View this file on GitHub
Last update: 2025-01-10 00:00:54+09:00
Problem: https://judge.yosupo.jp/problem/point_add_rectangle_sum

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"
#include "../Utility/template.hpp"
#include "../Datastructure/dynamicseg.hpp"
#include "../Datastructure/online2dseg.hpp"

using S = ll;
S op(S l, S r) {
    return l + r;
}

S e() {
    return 0LL;
}

int main() {
    ll N, Q;
    cin >> N >> Q;
    online2dseg<S, op, e, int> seg(0, 1000000001, 0, 1000000001);
    map<int, map<int, ll>> val;

    rep(i, 0, N) {
        ll x, y, w;
        cin >> x >> y >> w;
        seg.apply(y, x, w);
    }

    while(Q--) {
        int t;
        cin >> t;
        if(t==0) {
            ll x, y, w;
            cin >> x >> y >> w;
            seg.apply(y, x, w);
        }
        else {
            ll l, d, r, u;
            cin >> l >> d >> r >> u;
            cout << seg.prod(d, u, l, r) << '\n';
        }
    }

}

#line 1 "verify/Datastructure_point_add_rec_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/dynamicseg.hpp"
template <class S, S (*op)(S, S), S (*e)(), class W> struct dynamicsegtree {
    W  min_pos;
    W  max_pos;
    dynamicsegtree(){} 
    dynamicsegtree(W l, W r) :  min_pos(l), max_pos(r) {};

    private:
        struct Node {
            W p;
            S x;
            S prod;
            Node* l;
            Node* r;
        
            Node(W pos, S v) : p(pos), x(v), prod(v) {
                l = nullptr;
                r = nullptr;
            }
        };
        using np = Node*;
        
        np root = nullptr;

        S val(np v) {
            return v != nullptr ? v -> prod : e(); 
        }

        np apply(np v, W p, S &s, W L, W R) {
            if(!v) {
                v = new Node(p, s);
                return v;
            }
            if(v-> p == p) {
                v -> x = s;
                v -> prod = op(val(v -> l), op(v -> x, val(v -> r)));
                return v;
            }
            
            W M = (L + R) >> 1;

            if(p < M) {
                if(v -> p < p) swap(p, v -> p), swap(s, v -> x);
                v -> l = apply(v -> l, p, s,  L, M);
            }
            else {
                if(v -> p > p) swap(p, v -> p), swap(s, v -> x);
                v -> r = apply(v -> r, p, s, M, R);
            }
            v -> prod = op(val(v -> l), op(v -> x, val(v -> r)));
            return v; 
        }

        S query(np v, W l, W r, W L, W R) {
            if(r <= L || R <= l) return e();
            if(!v) return e();
            if(l <= L && R <= r) return v -> prod;

            W M = (L + R) >> 1;
            S res = query(v -> l, l, r, L, M);
            if(l <= v -> p && v -> p < r) res = op(res, v -> x);
            return op(res, query(v -> r, l, r, M, R));
        }

    public:
        void set(W pos, S s) {
           root = apply(root, pos, s, min_pos, max_pos);
        }

        S  prod(W l, W r) {
            return query(root, l, r, min_pos, max_pos);
        }

};

/*
    @brief 動的セグ木
    @docs doc/dynamicseg.md
        
*/
#line 1 "Datastructure/online2dseg.hpp"
template <class S, S (*op)(S, S), S (*e)(), class W> struct online2dseg {

    W minh, maxh, minw, maxw;
    online2dseg(W sy, W ty, W sx, W tx) : minh(sy), maxh(ty), minw(sx), maxw(tx) {};

    private:
        struct Node {
            dynamicsegtree<S, op, e, W> st;
            Node* l;
            Node* r;
            
            Node(W L, W R) {
              st = dynamicsegtree<S, op, e, W>(L, R);
              l = nullptr;
              r = nullptr;
            }
        };

        using np = Node*;

        Node* root = nullptr;

        np apply(np v, W h, W w, S &s, W L, W R) {
            if(!v) v = new Node(minw, maxw);
            v -> st.set(w, op(v -> st.prod(w, w+1),  s));

            if(R - L == 1) return v;
            
            W M = (L + R) >> 1;
            if(h < M) v -> l = apply(v -> l, h, w, s, L, M);
            else v -> r = apply(v -> r, h, w, s, M, R);
            return v;
        }

        S query(np v, W sy, W ty, W sx, W tx, W L, W R) {
            if(R <= sy || ty <= L) return e();
            if(!v) return e();
            if(sy <= L && R <= ty) return v -> st.prod(sx, tx);

            W M = (L + R) >> 1;
            S l = query(v -> l, sy, ty, sx, tx, L, M);
            S r = query(v -> r, sy, ty, sx, tx, M, R);
            return op(l, r);
        }
        
    public:
        void apply(W y, W x, S s) {
            root = apply(root, y, x, s, minh, maxh);
            return;
        }

        S prod(W sy, W ty, W sx, W tx) {
            return query(root, sy, ty, sx, tx, minh, maxh);
        }

        
};


/*
@docs doc/2dseg.md
@brief 巨大なグリッドへの1点加算・矩形和
*/
#line 5 "verify/Datastructure_point_add_rec_sum.test.cpp"

using S = ll;
S op(S l, S r) {
    return l + r;
}

S e() {
    return 0LL;
}

int main() {
    ll N, Q;
    cin >> N >> Q;
    online2dseg<S, op, e, int> seg(0, 1000000001, 0, 1000000001);
    map<int, map<int, ll>> val;

    rep(i, 0, N) {
        ll x, y, w;
        cin >> x >> y >> w;
        seg.apply(y, x, w);
    }

    while(Q--) {
        int t;
        cin >> t;
        if(t==0) {
            ll x, y, w;
            cin >> x >> y >> w;
            seg.apply(y, x, w);
        }
        else {
            ll l, d, r, u;
            cin >> l >> d >> r >> u;
            cout << seg.prod(d, u, l, r) << '\n';
        }
    }

}