Dynamic Range Minimum Queries

input/code.cpp: In function 'int main()':
input/code.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     } else if (m < mins.size()) {
      |                ~~^~~~~~~~~~~~~

#include "iostream"
#include "cmath"
#include "climits"
#include "algorithm"
#include "vector"

int main() {
    int n, q;
    std::cin >> n >> q;
    int m = (std::sqrt(n));
    if (n > 0 && m == 0) m = 1;
    std::vector<int> array(n);
    std::vector<int> mins(m + 1);
    for (int i = 0; i < m; i++) {
        int Idx = i * m;
        for (int j = 0; j < m; j++) {
            if (Idx + j < n) {
                std::cin >> array[Idx + j];
            } else {
                break;
            }
        }
        if (Idx < n) {
            int end = std::min((i + 1) * m, n);
            mins[i] = *std::min_element(array.begin() + Idx, array.begin() + end);
        } else {
            mins[i] = INT_MAX;
        }
    }
    int rest = n - m * m;
    for (int i = 0; i < rest; i++) {
        std::cin >> array[m * m + i];
    }
    if (rest > 0) {
        mins[m] = *std::min_element(array.begin() + m * m, array.begin() + n);
    } else if (m < mins.size()) {
        mins[m] = INT_MAX;
    }
    std::vector<int> queries(3);
    for (int i = 0; i < q; i++) {
        std::cin >> queries[0] >> queries[1] >> queries[2];
        int idx = (queries[1] - 1) / m;
        if (queries[0] == 1) {
            array[queries[1] - 1] = queries[2];
            int block_start = idx * m;
            int block_end = std::min((idx + 1) * m, n);
            mins[idx] = *std::min_element(array.begin() + block_start, array.begin() + block_end);
        } else {
            int tmp = INT_MAX;
            int idx2 = (queries[2] - 1) / m;
            if (idx == idx2) {
                for (int j = queries[1] - 1; j <= queries[2] - 1; ++j) {
                    tmp = std::min(tmp, array[j]);
                }
            } else {
                for (int j = queries[1] - 1; j < (idx + 1) * m; ++j) {
                    tmp = std::min(tmp, array[j]);
                }
                for (int j = idx + 1; j < idx2; ++j) {
                    tmp = std::min(tmp, mins[j]);
                }
                for (int j = idx2 * m; j <= queries[2] - 1; ++j) {
                    tmp = std::min(tmp, array[j]);
                }
            }
            std::cout << tmp << std::endl;
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED