Initial commit

6 files changed, 188 insertions, 0 deletions

diff --git a/05_range_queries/a.out b/05_range_queries/a.out
new file mode 100755
index 0000000..27b6efc
--- /dev/null
+++ b/05_range_queries/a.out
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 <algorithm>
+#include <iostream>
+#include <vector>
+
+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<size_t> 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 <algorithm>
+#include <iostream>
+#include <vector>
+
+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<long long> 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 <algorithm>
+#include <iostream>
+#include <vector>
+
+int main() {
+        size_t n, q;
+        std::cin >> n >> q;
+        std::vector<int> 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 <iostream>
+#include <limits>
+#include <vector>
+
+int minrange(std::vector<int>& 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<int>::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<int>& 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<int> 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 <iostream>
+#include <vector>
+
+int main() {
+        int n, q, x, y;
+        std::cin >> n >> q;
+        std::vector<long long> 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";
+        }
+}