test/library_checker/data_structure/rectangle_add_point_get.test.cpp

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

Depends on

• lib/data_structure/range_tree.hpp

Code

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

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

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

    int n, q; cin >> n >> q;
    vector<int> l(n), d(n), r(n), u(n);
    vector<long long> w(n);
    RangeTree<int, long long> rt;
    for(int i = 0; i < n; i++){
        cin >> l[i] >> d[i] >> r[i] >> u[i] >> w[i];
        rt.add_point(l[i], d[i]);
        rt.add_point(l[i], u[i]);
        rt.add_point(r[i], d[i]);
        rt.add_point(r[i], u[i]);
    }
    using T = tuple<int, int, int, int, int, long long>;
    vector<T> query(q);
    for(int i = 0; i < q; i++){
        int T; cin >> T;
        if(T == 0){
            int L, D, R, U;
            long long W;
            cin >> L >> D >> R >> U >> W;
            rt.add_point(L, D);
            rt.add_point(L, U);
            rt.add_point(R, D);
            rt.add_point(R, U);
            query[i] = {T, L, D, R, U, W};
        }else{
            int X, Y; cin >> X >> Y;
            query[i] = {T, X, Y, 0, 0, 0};
        }
    }
    rt.build();
    for(int i = 0; i < n; i++){
        rt.add(l[i], d[i], w[i]);
        rt.add(l[i], u[i], -w[i]);
        rt.add(r[i], d[i], -w[i]);
        rt.add(r[i], u[i], w[i]);
    }
    for(int i = 0; i < q; i++){
        auto [T, A, B, C, D, E] = query[i];
        if(T == 0){
            rt.add(A, B, E);
            rt.add(A, D, -E);
            rt.add(C, B, -E);
            rt.add(C, D, E);
        }else{
            cout << rt.sum(A + 1, B + 1) << "\n";
        }
    }
}

#line 1 "test/library_checker/data_structure/rectangle_add_point_get.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_add_point_get"
#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/rectangle_add_point_get.test.cpp"

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

    int n, q; cin >> n >> q;
    vector<int> l(n), d(n), r(n), u(n);
    vector<long long> w(n);
    RangeTree<int, long long> rt;
    for(int i = 0; i < n; i++){
        cin >> l[i] >> d[i] >> r[i] >> u[i] >> w[i];
        rt.add_point(l[i], d[i]);
        rt.add_point(l[i], u[i]);
        rt.add_point(r[i], d[i]);
        rt.add_point(r[i], u[i]);
    }
    using T = tuple<int, int, int, int, int, long long>;
    vector<T> query(q);
    for(int i = 0; i < q; i++){
        int T; cin >> T;
        if(T == 0){
            int L, D, R, U;
            long long W;
            cin >> L >> D >> R >> U >> W;
            rt.add_point(L, D);
            rt.add_point(L, U);
            rt.add_point(R, D);
            rt.add_point(R, U);
            query[i] = {T, L, D, R, U, W};
        }else{
            int X, Y; cin >> X >> Y;
            query[i] = {T, X, Y, 0, 0, 0};
        }
    }
    rt.build();
    for(int i = 0; i < n; i++){
        rt.add(l[i], d[i], w[i]);
        rt.add(l[i], u[i], -w[i]);
        rt.add(r[i], d[i], -w[i]);
        rt.add(r[i], u[i], w[i]);
    }
    for(int i = 0; i < q; i++){
        auto [T, A, B, C, D, E] = query[i];
        if(T == 0){
            rt.add(A, B, E);
            rt.add(A, D, -E);
            rt.add(C, B, -E);
            rt.add(C, D, E);
        }else{
            cout << rt.sum(A + 1, B + 1) << "\n";
        }
    }
}

Back to top page