kyopro_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub dyktr06/kyopro_library

:heavy_check_mark: test/library_checker/data_structure/point_add_rectangle_sum.test.cpp

Depends on

Code

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

#include "../../../lib/data_structure/dynamic_binary_indexed_tree_2d.hpp"
#include "../../../lib/others/compression.hpp"

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

    int n, q; cin >> n >> q;
    vector<int> xl, yl;
    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);
        xl.push_back(x);
        yl.push_back(y);
    }
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        if(t == 0){
            int x, y, w; cin >> x >> y >> w;
            xl.push_back(x);
            yl.push_back(y);
            query.emplace_back(t, x, y, w, 0);
        }else{
            int l, d, r, u; cin >> l >> d >> r >> u;
            xl.push_back(l);
            xl.push_back(r);
            yl.push_back(d);
            yl.push_back(u);
            query.emplace_back(t, l, d, r, u);
        }
    }
    compress<int> xc(xl), yc(yl);
    DynamicBinaryIndexedTree2D<long long> BIT(xc.size(), yc.size());
    for(int i = 0; i < n; i++){
        auto [x, y, w] = point[i];
        BIT.add(xc.get(x), yc.get(y), w);
    }
    for(int i = 0; i < q; i++){
        auto [t, a, b, c, d] = query[i];
        if(t == 0){
            BIT.add(xc.get(a), yc.get(b), c);
        }else{
            cout << BIT.sum(xc.get(a), yc.get(b), xc.get(c), yc.get(d)) << "\n";
        }
    }
}
#line 1 "test/library_checker/data_structure/point_add_rectangle_sum.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/dynamic_binary_indexed_tree_2d.hpp"

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

/*
    DynamicBinaryIndexedTree<S, T>(n) : BITをサイズnで構築
    add(i, x) : i 番目の要素に加算します。 O(log(n)^2)
    sum(l, r) : [l, r) の区間和を取得します。O(log(n)^2)

    (以下の機能を使うには、0 <= i < N において、A_i >= 0 である必要があります。)
    lower_bound(x) : A_0 + A_1 + ... + A_y >= x となる最小の y を求めます。O(log(n))
*/

template <typename S, typename T>
struct DynamicBinaryIndexedTree{
    S N;
    unordered_map<S, T> data;
    DynamicBinaryIndexedTree(S _N) : N(_N + 1){
    }

    void add(S i, const T &x){
        for(++i; i < N; i += i & -i) data[i] += x;
    }

    T sum(int i){
        if(i < 0){
            return 0;
        }
        T ans = 0;
        while(i > 0){
            const auto iter = data.find(i);
            if(iter != data.end()){
                ans += iter->second;
            }
            i -= i & -i;
        }
        return ans;
    }

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

    T operator[](S i){
        return sum(i + 1) - sum(i);
    }

    S lower_bound(T x){
        if(x <= 0){
            return 0;
        }
        S v = 0, r = 1;
        while(r < N) r = r << 1;
        for(S len = r; len > 0; len = len >> 1){
            if(v + len < N && data[v + len] < x){
                x -= data[v + len];
                v += len;
            }
        }
        return v;
    }
};
#line 4 "lib/data_structure/dynamic_binary_indexed_tree_2d.hpp"

/*
    DynamicBinaryIndexedTree2D<S, T>(h, w) : BIT2Dをサイズh*wで構築
    add(x, y, v) : (x, y) に v を加算します。
    sum(x1, y1, x2, y2) : [(x1, y1), (x2, y2)] の和を取得します。
*/

template <typename T>
struct DynamicBinaryIndexedTree2D{
    using BIT = DynamicBinaryIndexedTree<int, T>;
    int H, W;
    vector<BIT *> bit;
    DynamicBinaryIndexedTree2D(int h, int w) : H(h + 1), W(w){
        for(int i = 0; i < H; i++){
            bit.push_back(new BIT(W));
        }
    }

    void add(int i, int j, const T &x){
        for(++i; i < H; i += i & -i) (*bit[i]).add(j, x);
    }

    T sum(int x, int y){
        if(x < 0 || y < 0){
            return 0;
        }
        T res = 0;
        while(x > 0){
            res += (*bit[x]).sum(y);
            x -= x & -x;
        }
        return res;
    }

    T sum(int x1, int y1, int x2, int y2){
        T res = 0;
        while(x1 != x2){
            if(x1 < x2){
                res += (*bit[x2]).sum(y1, y2);
                x2 -= x2 & -x2;
            } else{
                res -= (*bit[x1]).sum(y1, y2);
                x1 -= x1 & -x1;
            }
        }
        return res;
    }
};
#line 2 "lib/others/compression.hpp"

/**
 * @brief Compression (座標圧縮)
 * @docs docs/others/compression.md
 */

#line 10 "lib/others/compression.hpp"

template <typename T>
struct compress{
    std::vector<T> sorted;
    std::vector<int> compressed;

    compress(const std::vector<T> &vec){
        int n = vec.size();
        compressed.resize(n);
        for(T x : vec){
            sorted.emplace_back(x);
        }
        std::sort(sorted.begin(), sorted.end());
        sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
        for(int i = 0; i < n; ++i){
            compressed[i] = std::lower_bound(sorted.begin(), sorted.end(), vec[i]) - sorted.begin();
        }
    }

    int get(const T &x) const{
        return std::lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
    }

    T inv(const int x) const{
        return sorted[x];
    }

    size_t size() const{
        return sorted.size();
    }

    std::vector<int> getCompressed() const{
        return compressed;
    }
};
#line 7 "test/library_checker/data_structure/point_add_rectangle_sum.test.cpp"

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

    int n, q; cin >> n >> q;
    vector<int> xl, yl;
    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);
        xl.push_back(x);
        yl.push_back(y);
    }
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        if(t == 0){
            int x, y, w; cin >> x >> y >> w;
            xl.push_back(x);
            yl.push_back(y);
            query.emplace_back(t, x, y, w, 0);
        }else{
            int l, d, r, u; cin >> l >> d >> r >> u;
            xl.push_back(l);
            xl.push_back(r);
            yl.push_back(d);
            yl.push_back(u);
            query.emplace_back(t, l, d, r, u);
        }
    }
    compress<int> xc(xl), yc(yl);
    DynamicBinaryIndexedTree2D<long long> BIT(xc.size(), yc.size());
    for(int i = 0; i < n; i++){
        auto [x, y, w] = point[i];
        BIT.add(xc.get(x), yc.get(y), w);
    }
    for(int i = 0; i < q; i++){
        auto [t, a, b, c, d] = query[i];
        if(t == 0){
            BIT.add(xc.get(a), yc.get(b), c);
        }else{
            cout << BIT.sum(xc.get(a), yc.get(b), xc.get(c), yc.get(d)) << "\n";
        }
    }
}
Back to top page