test/library_checker/data_structure/point_add_rectangle_sum_rt.test.cpp

View this file on GitHub
Last update: 2024-05-04 18:06:16+09:00
Problem: https://judge.yosupo.jp/problem/point_add_rectangle_sum

Depends on

lib/data_structure/range_tree.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/data_structure/range_tree.hpp"

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, q; cin >> n >> q;
    RangeTree<int, long long> tree;
    vector<tuple<int, int, int>> point;
    vector<tuple<int, int, int, int, int>> query;
    for(int i = 0; i < n; i++){
        int x, y, w; cin >> x >> y >> w;
        point.emplace_back(x, y, w);
        tree.add_point(x, y);
    }
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        if(t == 0){
            int x, y, w; cin >> x >> y >> w;
            tree.add_point(x, y);
            query.emplace_back(t, x, y, w, 0);
        }else{
            int l, d, r, u; cin >> l >> d >> r >> u;
            query.emplace_back(t, l, d, r, u);
        }
    }
    tree.build();
    for(int i = 0; i < n; i++){
        auto [x, y, w] = point[i];
        tree.add(x, y, w);
    }
    for(int i = 0; i < q; i++){
        auto [t, a, b, c, d] = query[i];
        if(t == 0){
            tree.add(a, b, c);
        }else{
            cout << tree.sum(a, b, c, d) << "\n";
        }
    }
}

#line 1 "test/library_checker/data_structure/point_add_rectangle_sum_rt.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/data_structure/range_tree.hpp"

template <typename S, typename T>
struct RangeTree{
    struct BinaryIndexedTree{
        int N;
        vector<T> BIT;
        BinaryIndexedTree() {}

        void init(int size){
            N = size;
            BIT.assign(N + 1, 0);
        }

        T get(int i){
            return sum(i + 1) - sum(i);
        }

        void add(int i, T x){
            ++i;
            while(i <= N){
                BIT[i] += x;
                i += i & -i;
            }
        }

        T sum(int i) const {
            T ans = 0;
            while(i > 0){
                ans += BIT[i];
                i -= i & -i;
            }
            return ans;
        }

        T sum(int L, int R) const {
            return sum(R) - sum(L);
        }
    };

    using P = pair<S, S>;
    S N, M;
    vector<BinaryIndexedTree> bit;
    vector<vector<S>> ys;
    vector<P> ps;

    RangeTree() {}

    void add_point(S x, S y){
        ps.push_back(make_pair(x, y));
    }

    void build(){
        sort(ps.begin(), ps.end());
        ps.erase(unique(ps.begin(), ps.end()), ps.end());

        N = ps.size();
        bit.resize(N + 1);
        ys.resize(N + 1);
        for(int i = 0; i <= N; ++i){
            int j = i + 1;
            while(j <= N){
                ys[j].push_back(ps[i].second);
                j += j & -j;
            }

            sort(ys[i].begin(), ys[i].end());
            ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
            bit[i].init(ys[i].size());
        }
    }

    int id(S x) const {
        auto f = [](const P &a, const P &b){
            return a.first < b.first;
        };
        return lower_bound(ps.begin(), ps.end(), make_pair(x, S()), f) - ps.begin();
    }

    int id(int i, S y) const {
        return lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin();
    }

    void add(S x, S y, T a){
        int i = lower_bound(ps.begin(), ps.end(), make_pair(x, y)) - ps.begin();
        assert(ps[i] == make_pair(x, y));
        ++i;
        while(i <= N){
            bit[i].add(id(i, y), a);
            i += i & -i;
        }
    }

    T sum(S x, S y) const {
        T ret = T();
        int a = id(x);
        while(a > 0){
            ret += bit[a].sum(id(a, y));
            a -= a & -a;
        }
        return ret;
    }

    // [(xl, yl), (xr, yr))
    T sum(S xl, S yl, S xr, S yr) const {
        T ret = T();
        int a = id(xl), b = id(xr);
        while(a != b) {
            if(a < b){
                ret += bit[b].sum(id(b, yl), id(b, yr));
                b -= b & -b;
            } else{
                ret -= bit[a].sum(id(a, yl), id(a, yr));
                a -= a & -a;
            }
        }
        return ret;
    }
};
#line 6 "test/library_checker/data_structure/point_add_rectangle_sum_rt.test.cpp"

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, q; cin >> n >> q;
    RangeTree<int, long long> tree;
    vector<tuple<int, int, int>> point;
    vector<tuple<int, int, int, int, int>> query;
    for(int i = 0; i < n; i++){
        int x, y, w; cin >> x >> y >> w;
        point.emplace_back(x, y, w);
        tree.add_point(x, y);
    }
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        if(t == 0){
            int x, y, w; cin >> x >> y >> w;
            tree.add_point(x, y);
            query.emplace_back(t, x, y, w, 0);
        }else{
            int l, d, r, u; cin >> l >> d >> r >> u;
            query.emplace_back(t, l, d, r, u);
        }
    }
    tree.build();
    for(int i = 0; i < n; i++){
        auto [x, y, w] = point[i];
        tree.add(x, y, w);
    }
    for(int i = 0; i < q; i++){
        auto [t, a, b, c, d] = query[i];
        if(t == 0){
            tree.add(a, b, c);
        }else{
            cout << tree.sum(a, b, c, d) << "\n";
        }
    }
}