SQRT Decompostion MIN / MAX

#include <bits/stdc++.h>
using namespace std;

const int maxN = 2 * 1e5 + 100;
const int block_size = 450;
int64_t input[maxN];
int64_t blocks[block_size];

int64_t query (int l,int r) {
    int64_t min_ = LLONG_MAX;
    int block_l = l / block_size,block_r = r / block_size;
    if (block_l == block_r) {
        for (int i = l; i <= r; ++i) min_ = min(min_,input[i]);
    } else {
        int end = (block_l + 1) * block_size - 1;
        for (int i = l; i <= end; ++i) min_ = min(min_,input[i]);
        for (int i = block_l + 1; i < block_r; ++i) min_ = min(min_,blocks[i]);
        for (int i = block_r * block_size; i <= r; ++i) min_ = min(min_,input[i]);
    }
    return min_;
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         int n,k;
         cin >> n >> k;
         for (int i = 0; i < n; ++i) cin >> input[i];
         for (int i = 0; i < block_size; ++i) blocks[i] = LLONG_MAX;
         for (int i = 0; i < n; ++i) blocks[i / block_size] = min(blocks[i / block_size],input[i]);
         if (k == 1) {
             cout << query(0,n - 1) << '\n';
         } else if (k == 2) {
             int64_t max_ = LLONG_MIN;
             for (int i = 0; i < n - 1; ++i) {
                 int l1 = 0,r1 = i;
                 int l2 = i + 1,r2 = n - 1;
                 max_ = max(max_,max(query(l1,r1),query(l2,r2)));
             }
             cout << max_ << '\n';
         } else {
             int64_t max_ = LLONG_MIN;
             for (int i = 0; i < n; ++i) max_ = max(input[i],max_);
             cout << max_ << '\n';
         }
     }
     //~ cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}