1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
 * @uni_kakurenbo
 * https://github.com/uni-kakurenbo/competitive-programming-workspace
 *
 * CC0 1.0  http://creativecommons.org/publicdomain/zero/1.0/deed.ja
 */
/* #language C++ 20 GCC */

#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"

#include "sneaky/enforce_int128_enable.hpp"

#include <iostream><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <memory_resource><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.

#include "snippet/aliases.hpp"
#include "snippet/fast_io.hpp"
#include "snippet/iterations.hpp"
#include "adaptor/vector.hpp"
#include "adaptor/map.hpp"
#include "adaptor/io.hpp"
#include "iterable/compressed.hpp"
#include "view/zip.hpp"
#include "data_structure/dynamic_segment_tree.hpp"
#include "action/range_sum.hpp"
#include "iterable/operation.hpp"

signed main() {
    uni::i32 n, q; input >> n >> q;
    uni::vector<uni::i32> x(n), y(n), w(n), inds(n);<--- Shadowed declaration<--- Shadowed declaration

    input >> uni::views::zip(x, y, w);
    std::iota(ALL(inds), 0);

    debug(inds, x, y, w);

    inds.sort([&](uni::i32 i, uni::i32 j) { return x[i] < x[j]; });
    x = uni::ordered_by(x, inds), y = uni::ordered_by(y, inds), w = uni::ordered_by(w, inds);
    debug(inds, x, y, w);

    uni::compressed comp_y(y);

    using segtree = uni::persistent_dynamic_segment_tree<uni::actions::range_sum<uni::i64>>;

    std::vector<segtree> storage;
    segtree data(n);

    storage.push_back(data);
    ITR(y, w, uni::views::zip(comp_y, w)) {<--- Shadow variable<--- Shadow variable
        storage.emplace_back(data.add(y, w));
        debug(data);
    }
    debug(storage);

    REP(q) {
        uni::i32 l, d, r, u; input >> l >> d >> r >> u;

        auto nl = std::ranges::lower_bound(x, l) - std::ranges::begin(x);
        auto nr = std::ranges::lower_bound(x, r) - std::ranges::begin(x);

        auto nd = comp_y.rank(d);
        auto nu = comp_y.rank(u);

        debug(l, d, r, u);
        debug(nl, nr);
        auto ans = storage[nr](nd, nu).fold() + -storage[nl](nd, nu).fold();
        print(ans);
    }
}