#include namespace MyLib { template class LiteralSegmentTree { protected: std::vector> containers; public: constexpr LiteralSegmentTree(const std::vector& initializer) { containers.clear(); if (initializer.size() == 0) return; else if (initializer.size() == 1) { containers.emplace_back(1, initializer[0]); return; } uint_fast32_t l = 0, r = 30; while (l + 1 < r) { const auto c = (l + r) >> 1; if (((uint_fast32_t)1 << c) < initializer.size()) l = c; else r = c; } containers.emplace_back((uint_fast32_t)1 << r); uint_fast32_t i; for (i = 0; i != initializer.size(); ++i) containers[0][i] = initializer[i]; for (; i != ((uint_fast32_t)1 << r); ++i) containers[0][i] = default_value; for (--r; r != 0; --r) { containers.emplace_back((uint_fast32_t)1 << r); for (i = 0; i != ((uint_fast32_t)1 << r); ++i) containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]); } containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1])); } constexpr LiteralSegmentTree(std::vector&& initializer) { containers.clear(); if (initializer.size() == 0) return; uint_fast32_t l = 0, r = 30; while (l + 1 < r) { const auto c = (l + r) >> 1; if (((uint_fast32_t)1 << c) < initializer.size()) l = c; else r = c; } containers.emplace_back(std::move(initializer)); containers[0].resize((uint_fast32_t)1 << r, default_value); uint_fast32_t i; for (--r; r != 0; --r) { containers.emplace_back((uint_fast32_t)1 << r); for (i = 0; i != ((uint_fast32_t)1 << r); ++i) containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]); } containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1])); } constexpr LiteralSegmentTree(const uint_fast32_t n) : LiteralSegmentTree(std::vector(n, default_value)) { } constexpr LiteralSegmentTree(const uint_fast32_t n, const T initial_value) : LiteralSegmentTree(std::vector(n, initial_value)) { } constexpr T operator[](uint_fast32_t index) const noexcept { return containers[0][index]; } constexpr uint_fast32_t size() const noexcept { return containers[0].size(); } constexpr uint_fast32_t layer() const noexcept { return containers.size(); } constexpr T update(uint_fast32_t index, const T value) noexcept { containers[0][index] = value; index >>= 1; for (uint_fast32_t i = 1; i != containers.size(); ++i, index >>= 1) containers[i][index] = Picker()(containers[i - 1][index << 1], containers[i - 1][(index << 1) | 1]); return value; } constexpr T range_pick_up(uint_fast32_t first_index, uint_fast32_t end_index) const noexcept { if (containers.size() == 0 || end_index > containers[0].size()) return default_value; T ret_l = default_value, ret_r = default_value; for (uint_fast32_t cur_layer = 0; first_index < end_index; first_index >>= 1, end_index >>= 1, ++cur_layer) { if (first_index & 1) ret_l = Picker()(ret_l, containers[cur_layer][first_index]), ++first_index; if (end_index & 1) ret_r = Picker()(containers[cur_layer][end_index - 1], ret_r); } return Picker()(ret_l, ret_r); } }; } // セグメントツリー解法 static inline constexpr std::vector solve(const uint_fast32_t N, const uint_fast32_t Q, std::vector&& A, std::vector& X, const std::vector& Y, const std::vector& L, const std::vector& R) noexcept { uint_fast64_t sum = 0; std::vector ans(Q); MyLib::LiteralSegmentTree, 0> lst(std::move(A)); MyLib::LiteralSegmentTree, 0> imos_weight(N + 1, 0); for (uint_fast32_t i = 0; i != Q; ++i) { const uint_fast32_t weight = imos_weight.range_pick_up(0, X[i]); // imos 法で一点の重みを取得する sum -= lst[X[i] - 1] * weight; lst.update(X[i] - 1, Y[i]); sum += lst[X[i] - 1] * weight; ans[i] = (sum += lst.range_pick_up(L[i] - 1, R[i])); imos_weight.update(L[i] - 1, imos_weight[L[i] - 1] + 1), imos_weight.update(R[i], imos_weight[R[i]] - 1); // imos 法で区間の重みを増やす } return ans; } static inline void output(const uint_fast32_t Q, const std::vector& ans) noexcept { for (uint_fast32_t i = 0; i != Q; ++i) std::cout << ans[i] << '\n'; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); uint_fast32_t N, Q, i; std::cin >> N; std::vector A(N); for (i = 0; i != N; ++i) std::cin >> A[i]; std::cin >> Q; std::vector X(Q), Y(Q), L(Q), R(Q); for (i = 0; i != Q; ++i) std::cin >> X[i] >> Y[i] >> L[i] >> R[i]; output(Q, solve(N, Q, std::move(A), X, Y, L, R)); return 0; }