cpp_library

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

View the Project on GitHub toyama1710/cpp_library

:heavy_check_mark: test/yosupo/rectangle_sum1.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"
// header file section
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

#include "../../segment_tree/persistent_segment_tree.hpp"
#include "../../util/coordinate_compression.hpp"

using namespace std;
using llong = long long;

struct Monoid {
    using value_type = llong;
    static llong operation(llong a, llong b) {
        return a + b;
    };
    static llong identity() {
        return 0;
    }
};

llong n, q;
vector<PersistentSegmentTree<Monoid>> v;
vector<tuple<llong, llong, llong>> p;
CoordinateCompressionBuilder<llong> x_axis_builder;
CoordinateCompressionBuilder<llong> y_axis_builder;

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

    for (int i = 0; i < n; i++) {
        llong x, y, w;
        cin >> x >> y >> w;
        p.push_back(tie(y, x, w));
        x_axis_builder.push(x);
        y_axis_builder.push(y);
    }

    sort(p.begin(), p.end());
    auto x_axis = x_axis_builder.build();
    auto y_axis = y_axis_builder.build();

    v.push_back(PersistentSegmentTree<Monoid>(x_axis.size()));

    for (int i = 0; i < p.size(); i++) {
        llong x, y, w;
        tie(y, x, w) = p[i];
        x = x_axis.zip(x);
        y = y_axis.zip(y);

        if (v.size() <= y) {
            v.push_back(v[y - 1]);
        }

        v[y] = v[y].update(x, v[y][x] + w);
    }

    for (int i = 0; i < q; i++) {
        llong l, d, r, u;
        cin >> l >> d >> r >> u;

        l = x_axis.zip(l);
        r = x_axis.zip(r);
        d = y_axis.zip(d) - 1;
        u = y_axis.zip(u) - 1;

        if (d >= 0)
            cout << v[u].fold(l, r) - v[d].fold(l, r) << '\n';
        else if (u >= 0)
            cout << v[u].fold(l, r) << '\n';
        else
            cout << 0 << '\n';
    }

    return 0;
};
#line 1 "test/yosupo/rectangle_sum1.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"
// header file section
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

#line 1 "segment_tree/persistent_segment_tree.hpp"



#include <cstddef>
#include <cstdint>
#line 7 "segment_tree/persistent_segment_tree.hpp"
#include <iterator>
#line 9 "segment_tree/persistent_segment_tree.hpp"

template <class Monoid>
struct PersistentSegmentTree {
    using uint = size_t;
    using T = typename Monoid::value_type;

    struct Node {
        T dat;
        Node *l = nullptr, *r = nullptr;

        Node(T dat) : dat(dat){};
    };

    Node *root;
    uint n;

    Node *merge_node(Node *lch, Node *rch) {
        T l = (lch ? lch->dat : Monoid::identity());
        T r = (rch ? rch->dat : Monoid::identity());
        Node *ret = new Node(Monoid::operation(l, r));
        ret->l = lch;
        ret->r = rch;

        return ret;
    };

    PersistentSegmentTree(const PersistentSegmentTree &) = default;

    PersistentSegmentTree &operator=(const PersistentSegmentTree &) = default;

    PersistentSegmentTree(uint n, Node *r) : root(r), n(n){};

    PersistentSegmentTree(uint n)
        : root(alloc(0, n, std::vector<T>(n, Monoid::identity()))), n(n){};

    template <class InputItr>
    PersistentSegmentTree(const InputItr first, const InputItr last)
        : n(std::distance(first, last)),
          root(alloc(0, n, std::vector<T>(first, last))){};

    Node *alloc(uint nl, uint nr, const std::vector<T> &v) {
        if (nr - nl <= 1)
            return new Node(v[nl]);
        else
            return merge_node(alloc(nl, (nl + nr) / 2, v),
                              alloc((nl + nr) / 2, nr, v));
    };

    const T fold(uint l, uint r) const {
        return fold(l, r, 0, n, root);
    };

    const T fold(uint ql, uint qr, uint nl, uint nr, const Node *np) const {
        if (np == nullptr || qr <= nl || nr <= ql)
            return Monoid::identity();

        else if (ql <= nl && nr <= qr)
            return np->dat;

        else
            return Monoid::operation(fold(ql, qr, nl, (nl + nr) / 2, np->l),
                                     fold(ql, qr, (nl + nr) / 2, nr, np->r));
    };

    PersistentSegmentTree update(uint idx, T d) {
        return set(idx, d);
    };

    PersistentSegmentTree set(uint idx, T d) {
        return PersistentSegmentTree(n, update(0, n, idx, d, root));
    };

    Node *update(uint nl, uint nr, uint idx, T d, Node *np) {
        if (idx < nl || nr <= idx)
            return np;
        else if (nr - nl == 1)
            return new Node(d);
        else
            return merge_node(update(nl, (nl + nr) / 2, idx, d, np->l),
                              update((nl + nr) / 2, nr, idx, d, np->r));
    };

    PersistentSegmentTree get_tree() {
        return *this;
    };

    T operator[](uint idx) {
        return fold(idx, idx + 1, 0, n, root);
    };
};


#line 1 "util/coordinate_compression.hpp"


#line 5 "util/coordinate_compression.hpp"

template <class T>
struct CoordinateCompression {
    std::vector<T> p;

    template <class InputItr>
    CoordinateCompression(InputItr first, InputItr last) : p(first, last) {
        std::sort(p.begin(), p.end());
        p.erase(unique(p.begin(), p.end()), p.end());
    };
    int zip(T x) {
        return std::lower_bound(p.begin(), p.end(), x) - p.begin();
    };
    T unzip(int x) {
        return p[x];
    };
    int size() {
        return p.size();
    };
};

template <class T>
struct CoordinateCompressionBuilder {
    std::vector<T> p;

    CoordinateCompressionBuilder() = default;
    template <class InputItr>
    CoordinateCompressionBuilder(InputItr first, InputItr last)
        : p(first, last){};
    void push(T x) {
        p.push_back(x);
    };
    CoordinateCompression<T> build() {
        return CoordinateCompression<T>(p.begin(), p.end());
    };
};


#line 19 "test/yosupo/rectangle_sum1.test.cpp"

using namespace std;
using llong = long long;

struct Monoid {
    using value_type = llong;
    static llong operation(llong a, llong b) {
        return a + b;
    };
    static llong identity() {
        return 0;
    }
};

llong n, q;
vector<PersistentSegmentTree<Monoid>> v;
vector<tuple<llong, llong, llong>> p;
CoordinateCompressionBuilder<llong> x_axis_builder;
CoordinateCompressionBuilder<llong> y_axis_builder;

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

    for (int i = 0; i < n; i++) {
        llong x, y, w;
        cin >> x >> y >> w;
        p.push_back(tie(y, x, w));
        x_axis_builder.push(x);
        y_axis_builder.push(y);
    }

    sort(p.begin(), p.end());
    auto x_axis = x_axis_builder.build();
    auto y_axis = y_axis_builder.build();

    v.push_back(PersistentSegmentTree<Monoid>(x_axis.size()));

    for (int i = 0; i < p.size(); i++) {
        llong x, y, w;
        tie(y, x, w) = p[i];
        x = x_axis.zip(x);
        y = y_axis.zip(y);

        if (v.size() <= y) {
            v.push_back(v[y - 1]);
        }

        v[y] = v[y].update(x, v[y][x] + w);
    }

    for (int i = 0; i < q; i++) {
        llong l, d, r, u;
        cin >> l >> d >> r >> u;

        l = x_axis.zip(l);
        r = x_axis.zip(r);
        d = y_axis.zip(d) - 1;
        u = y_axis.zip(u) - 1;

        if (d >= 0)
            cout << v[u].fold(l, r) - v[d].fold(l, r) << '\n';
        else if (u >= 0)
            cout << v[u].fold(l, r) << '\n';
        else
            cout << 0 << '\n';
    }

    return 0;
};
Back to top page