From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- 05_range_queries/a.out | Bin 0 -> 15808 bytes .../dynamic_range_minimum_queries_1649.cpp | 54 +++++++++++++++++++++ .../dynamic_range_sum_queries_1648.cpp | 50 +++++++++++++++++++ 05_range_queries/range_xor_queries_1650.cpp | 20 ++++++++ .../static_range_minimum_queries_1647.cpp | 47 ++++++++++++++++++ 05_range_queries/static_range_sum_queries_1646.cpp | 17 +++++++ 6 files changed, 188 insertions(+) create mode 100755 05_range_queries/a.out create mode 100644 05_range_queries/dynamic_range_minimum_queries_1649.cpp create mode 100644 05_range_queries/dynamic_range_sum_queries_1648.cpp create mode 100644 05_range_queries/range_xor_queries_1650.cpp create mode 100644 05_range_queries/static_range_minimum_queries_1647.cpp create mode 100644 05_range_queries/static_range_sum_queries_1646.cpp (limited to '05_range_queries') diff --git a/05_range_queries/a.out b/05_range_queries/a.out new file mode 100755 index 0000000..27b6efc Binary files /dev/null and b/05_range_queries/a.out differ diff --git a/05_range_queries/dynamic_range_minimum_queries_1649.cpp b/05_range_queries/dynamic_range_minimum_queries_1649.cpp new file mode 100644 index 0000000..c4d9b34 --- /dev/null +++ b/05_range_queries/dynamic_range_minimum_queries_1649.cpp @@ -0,0 +1,54 @@ +#include +#include +#include + +constexpr size_t inf = 1999999999; + +class SegmentTree { +public: + SegmentTree(size_t n) : m{pow2ceil(n)}, v(2*m, inf) {} + + void update(size_t i, size_t x) { + v[m+i-1] = x; + for (size_t p = (m+i-1)/2; p > 0; p /= 2) + v[p] = std::min(v[2*p], v[2*p+1]); + } + + size_t min(size_t a, size_t b) { return q(a-1, b, 1, 0, m); } + +private: + size_t m; + std::vector v; + static constexpr size_t pow2ceil(size_t x) { + size_t c; + for (c = 1; c < x; c *= 2) ; + return c; + } + + size_t q(size_t a, size_t b, size_t i, size_t l, size_t r) { + if (a == l && b == r) return v[i]; + size_t p{(l+r)/2}, s{inf}; + if (a < p) s = std::min(s, q(a, std::min(b, p), 2*i, l, p)); + if (b > p) s = std::min(s, q(std::max(a, p), b, 2*i+1, p, r)); + return s; + } +}; + +int main() { + size_t n, q; + std::cin >> n >> q; + SegmentTree t(n); + for (size_t i = 0; i < n; i++) { + size_t x; + std::cin >> x; + t.update(i+1, x); + } + for (size_t i = 0; i < q; i++) { + int u, a, b; + std::cin >> u >> a >> b; + if (u == 1) + t.update(a, b); + else + std::cout << t.min(a, b) << "\n"; + } +} diff --git a/05_range_queries/dynamic_range_sum_queries_1648.cpp b/05_range_queries/dynamic_range_sum_queries_1648.cpp new file mode 100644 index 0000000..ceb6b0c --- /dev/null +++ b/05_range_queries/dynamic_range_sum_queries_1648.cpp @@ -0,0 +1,50 @@ +#include +#include +#include + +class SumFenwickTree { +public: + SumFenwickTree(int n) : a(n+1) {} + long long sum(int l, int r) const { return psum(r) - psum(l-1); } + void update(int k, long long u) { add(k, u - sum(k, k));} + +private: + std::vector a; + + static int lsb(int i) { return i & -i; } + + long long psum(int i) const { + long long s = 0; + while (i > 0) { + s += a[i]; + i -= lsb(i); + } + return s; + } + + void add(int k, long long d) { + while (k < (int)a.size()) { + a[k] += d; + k += lsb(k); + } + } +}; + +int main() { + size_t n, q; + std::cin >> n >> q; + SumFenwickTree t(n); + for (size_t i = 0; i < n; i++) { + long long x; + std::cin >> x; + t.update(i+1, x); + } + for (size_t i = 0; i < q; i++) { + long long x, k, u; + std::cin >> x >> k >> u; + if (x == 1) + t.update(k, u); + else + std::cout << t.sum(k, u) << "\n"; + } +} diff --git a/05_range_queries/range_xor_queries_1650.cpp b/05_range_queries/range_xor_queries_1650.cpp new file mode 100644 index 0000000..e6a4500 --- /dev/null +++ b/05_range_queries/range_xor_queries_1650.cpp @@ -0,0 +1,20 @@ +#include +#include +#include + +int main() { + size_t n, q; + std::cin >> n >> q; + std::vector p(n); + for (size_t i = 0; i < n; i++) + std::cin >> p[i]; + for (size_t i = 1; i < n; i++) + p[i] ^= p[i-1]; + for (size_t i = 0; i < q; i++) { + int x, k, s; + std::cin >> x >> k; + s = p[k-1]; + if (x > 1) s ^= p[x-2]; + std::cout << s << "\n"; + } +} diff --git a/05_range_queries/static_range_minimum_queries_1647.cpp b/05_range_queries/static_range_minimum_queries_1647.cpp new file mode 100644 index 0000000..ef11438 --- /dev/null +++ b/05_range_queries/static_range_minimum_queries_1647.cpp @@ -0,0 +1,47 @@ +#include +#include +#include + +int minrange(std::vector& a, int x, int y, int i, int p, int l, int r) { + if (x == l && y == r) + return a[2*p-2-i]; + + if (x >= y) + return std::numeric_limits::max(); + + int lr = (l+r)/2; + return std::min( + minrange(a, std::max(x, l), std::min(y, lr), 2*i+2, p, l, lr), + minrange(a, std::max(x, lr), std::min(y, r), 2*i+1, p, lr, r) + ); +} + +void compute_mins(std::vector& a, int j, int n) { + for (int i = 0; i < n; i += 2) + a[j+n+i/2] = std::min(a[j+i], a[j+i+1]); +} + +int main() { + int n, q, x, y, p; + std::cin >> n >> q; + + // For simplicity, extend n to a power of 2 + for (p = 1; p < n; p <<= 1) ; + + std::vector a(2*p-1, 0); + for (int i = 0; i < n; i++) + std::cin >> a[i]; + + // a[p], a[p+1] ... a[p+p/2-1] are min of pairs + // a[p+p/2], a[p+p/2+1], ... a[p+p/2+p/4] are min of quads + // etc... + for (int i = 1, j = 0; i < p; i <<= 1) { + compute_mins(a, j, p/i); + j += p/i; + } + + for (int i = 0; i < q; i++) { + std::cin >> x >> y; + std::cout << minrange(a, x-1, y, 0, p, 0, p) << "\n"; + } +} diff --git a/05_range_queries/static_range_sum_queries_1646.cpp b/05_range_queries/static_range_sum_queries_1646.cpp new file mode 100644 index 0000000..7de69a2 --- /dev/null +++ b/05_range_queries/static_range_sum_queries_1646.cpp @@ -0,0 +1,17 @@ +#include +#include + +int main() { + int n, q, x, y; + std::cin >> n >> q; + std::vector a(n+1, 0); + for (int i = 1; i <= n; i++) { + std::cin >> a[i]; + a[i] += a[i-1]; + } + + for (int i = 0; i < q; i++) { + std::cin >> x >> y; + std::cout << a[y]-a[x-1] << "\n"; + } +} -- cgit v1.3