src/test/yosupo_point_add_rectangle_sum.cpp

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

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_rectangle_sum

#include "../segtree2d.hpp"
long op(long l, long r) { return l + r; }
long e() { return 0; }

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<array<int, 5>> qu(N + Q);
    segtree_2d<int, long, op, e> seg;
    rep(i, N) {
        int x, y, w;
        cin >> x >> y >> w;
        qu[i] = {0, x, y, w};
        seg.add_point(x, y);
    }
    rep(i, Q) {
        int t;
        cin >> t;
        if(t == 0) {
            int x, y, w;
            cin >> x >> y >> w;
            qu[i + N] = {0, x, y, w};
            seg.add_point(x, y);
        }
        else {
            int l, d, r, u;
            cin >> l >> d >> r >> u;
            qu[i + N] = {1, l, d, r, u};
        }
    }

    seg.build();
    for(auto a: qu) {
        if(a[0] == 0) {
            seg.add(a[1], a[2], a[3]);
        }
        else {
            cout << seg.range(a[1], a[3], a[2], a[4]) << "\n";
        }
    }
}

#line 1 "src/test/yosupo_point_add_rectangle_sum.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_rectangle_sum

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 3 "src/segtree.hpp"

template<class S, S (*op)(S, S), S (*e)()> struct segtree {
    int n;
    vector<S> d;
    segtree(): segtree(1) {}
    explicit segtree(int n_): segtree(vector<S>(n_, e())) {}
    explicit segtree(const vector<S>& a): n(__bit_ceil(si(a))), d(n * 2, e()) {
        rep(i, si(a)) d[n + i] = a[i];
        for(int i = n; --i;) d[i] = op(d[i * 2], d[i * 2 + 1]);
    }
    void set(int i, S x) {
        for(d[i += n] = x; i >>= 1;) d[i] = op(d[i * 2], d[i * 2 + 1]);
    }
    S get(int i) { return d[i + n]; }
    S prod(int l, int r) {
        S L = e(), R = e();
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) L = op(L, d[l++]);
            if(r & 1) R = op(d[--r], R);
        }
        return op(L, R);
    }
    template<typename F> int max_right(int l, F f) const {
        if(l == n) return n;
        l += n;
        S sm = e();
        do {
            while(~l & 1) l >>= 1;
            if(!f(op(sm, d[l]))) {
                while(l < n) {
                    l <<= 1;
                    if(f(op(sm, d[l]))) sm = op(sm, d[l++]);
                }
                return l - n;
            }
            sm = op(sm, d[l++]);
        } while((l & -l) != l);
        return n;
    }
    template<typename F> int min_left(int r, F f) const {
        if(!r) return 0;
        r += n;
        S sm = e();
        do {
            r--;
            while(r > 1 and r & 1) r >>= 1;
            if(!f(op(d[r], sm))) {
                while(r < n) {
                    r = (2 * r + 1);
                    if(f(op(d[r], sm))) sm = op(d[r--], sm);
                }
                return r + 1 - n;
            }
            sm = op(d[r], sm);
        } while((r & -r) != r);
        return 0;
    }
};

template<class T> using SegtreeFrom = segtree<typename T::S, T::op, T::e>;
#line 2 "src/segtree2d.hpp"

template<typename K, class S, S (*op)(S, S), S (*e)()> struct segtree_2d {
    int n;
    vector<segtree<S, op, e>> d;
    vector<vector<K>> ys;
    vector<pair<K, K>> ps;
    segtree_2d() {}
    void add_point(K x, K y) { ps.push_back({x, y}); }

    void build() {
        sort(all(ps));
        ps.erase(unique(all(ps)), ps.end());
        n = __bit_ceil(si(ps));
        ys.resize(2 * n);
        rep(i, si(ps)) ys[n + i] = {ps[i].se};
        for(int i = n; --i;) merge(all(ys[i * 2]), all(ys[i * 2 + 1]), back_inserter(ys[i]));

        d.resize(2 * n);
        for(int i = 1; i < 2 * n; i++) {
            d[i] = segtree<S, op, e>(si(ys[i]) + 1);
        }
    }

    void set(K x, K y, S v) {
        auto it = lower_bound(all(ps), make_pair(x, y));
        assert(it != ps.end() && it->fi == x && it->se == y);
        int k = it - ps.begin();
        for(k += n; k; k >>= 1) {
            auto it = lower_bound(all(ys[k]), y);
            assert(it != ys[k].end());
            int id = it - ys[k].begin();
            d[k].set(id, v);
        }
    }
    void add(K x, K y, S v) {
        auto it = lower_bound(all(ps), make_pair(x, y));
        assert(it != ps.end() && it->fi == x && it->se == y);
        int k = it - ps.begin();
        for(k += n; k; k >>= 1) {
            auto it = lower_bound(all(ys[k]), y);
            assert(it != ys[k].end());
            int id = it - ys[k].begin();
            d[k].set(id, op(d[k].get(id), v));
        }
    }

    S range(K lv, K rv, K dv, K uv) {
        if(dv >= uv) return e();
        int l = lower_bound(all(ps), make_pair(lv, -1)) - ps.begin();
        int r = lower_bound(all(ps), make_pair(rv, -1)) - ps.begin();

        S sml = e(), smr = e();
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) {
                int li = lower_bound(all(ys[l]), dv) - ys[l].begin();
                int ri = lower_bound(all(ys[l]), uv) - ys[l].begin();
                sml = op(sml, d[l].prod(li, ri));
                l++;
            }
            if(r & 1) {
                --r;
                int li = lower_bound(all(ys[r]), dv) - ys[r].begin();
                int ri = lower_bound(all(ys[r]), uv) - ys[r].begin();
                smr = op(d[r].prod(li, ri), smr);
            }
        }
        return op(sml, smr);
    }
};
#line 4 "src/test/yosupo_point_add_rectangle_sum.cpp"
long op(long l, long r) { return l + r; }
long e() { return 0; }

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<array<int, 5>> qu(N + Q);
    segtree_2d<int, long, op, e> seg;
    rep(i, N) {
        int x, y, w;
        cin >> x >> y >> w;
        qu[i] = {0, x, y, w};
        seg.add_point(x, y);
    }
    rep(i, Q) {
        int t;
        cin >> t;
        if(t == 0) {
            int x, y, w;
            cin >> x >> y >> w;
            qu[i + N] = {0, x, y, w};
            seg.add_point(x, y);
        }
        else {
            int l, d, r, u;
            cin >> l >> d >> r >> u;
            qu[i + N] = {1, l, d, r, u};
        }
    }

    seg.build();
    for(auto a: qu) {
        if(a[0] == 0) {
            seg.add(a[1], a[2], a[3]);
        }
        else {
            cout << seg.range(a[1], a[3], a[2], a[4]) << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	many_points_00	AC	1085 ms	176 MB
g++	many_queries_00	AC	848 ms	104 MB
g++	max_random_00	AC	1067 ms	155 MB
g++	max_random_01	AC	1045 ms	155 MB
g++	power_of_2_00	AC	501 ms	58 MB
g++	power_of_2_01	AC	483 ms	58 MB
g++	random_00	AC	328 ms	50 MB
g++	random_01	AC	389 ms	79 MB
g++	random_02	AC	501 ms	83 MB
g++	small_00	AC	7 ms	4 MB
g++	small_01	AC	6 ms	4 MB
g++	small_02	AC	6 ms	4 MB
g++	small_03	AC	6 ms	4 MB
g++	small_04	AC	6 ms	4 MB
g++	xy_concentrate_00	AC	940 ms	148 MB
g++	xy_concentrate_01	AC	986 ms	148 MB
g++	xy_concentrate_02	AC	967 ms	149 MB
clang++	example_00	AC	5 ms	4 MB
clang++	many_points_00	AC	2004 ms	176 MB
clang++	many_queries_00	AC	1379 ms	104 MB
clang++	max_random_00	AC	1809 ms	155 MB
clang++	max_random_01	AC	1597 ms	155 MB
clang++	power_of_2_00	AC	591 ms	58 MB
clang++	power_of_2_01	AC	570 ms	58 MB
clang++	random_00	AC	437 ms	50 MB
clang++	random_01	AC	579 ms	79 MB
clang++	random_02	AC	818 ms	83 MB
clang++	small_00	AC	7 ms	4 MB
clang++	small_01	AC	7 ms	4 MB
clang++	small_02	AC	6 ms	4 MB
clang++	small_03	AC	6 ms	4 MB
clang++	small_04	AC	8 ms	4 MB
clang++	xy_concentrate_00	AC	1784 ms	148 MB
clang++	xy_concentrate_01	AC	1519 ms	148 MB
clang++	xy_concentrate_02	AC	1621 ms	149 MB