872B - Maximum of Maximums of Minimums - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define T int t; cin>>t; while(t--)
#define ll long long
#define vec vector
#define all(x) x.begin(), x.end()
const int N=1e5+5, mod=1e9+7;
int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
int dy[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
template <typename Tmp>
struct sparse_table{
    vector<vector<Tmp>> ST;
    sparse_table(vector<Tmp> &A){
        int n = A.size();
        int LOG = 32 - __builtin_clz(n);
        ST = vector<vector<Tmp>>(LOG, vector<Tmp>(n+1));
        for (int i = 0; i < n; i++){
            ST[0][i] = A[i];
        }
        for (int i = 0; i < LOG - 1; i++){
            for (int j = 0; j < n - (1 << i); j++){
                ST[i + 1][j] = min(ST[i][j], ST[i][j + (1 << i)]);
            }
        }
    }
    Tmp range_min(int L, int R){
        int d = 31 - __builtin_clz(R - L + 1);
        Tmp op1=ST[d][L], op2=ST[d][R - (1 << d)+1];
        return ( op1 < op2 ? op1 : op2 );
    }
    ll query2(int l,int r)
    {
        int sz=r-l+1;
        ll ret=0;
        for(int i=0;i<22;i++)
        {
            if(sz&(1<<i))
            {
                ret=merge(ret, ST[l][i]);
                l+=(1<<i);
            }
        }
        return ret;
    }
};
int main(){
    ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
    int n, k; cin>>n>>k;
    vec<ll>x(n);
    for(auto &it: x) cin>>it;
    sparse_table sp(x);
    if(k==2){
        ll ans=-1e18;
        for(int i=0;i<n;i++){
            ans=max(ans, sp.range_min(0,i));
            if(i+1<n) ans=max(ans, sp.range_min(i+1,n-1));
        }
        cout<<ans;
    }
    else{
        sort(all(x));
        if(k==1) cout<<x[0];
        else cout<<x[n-1];
    }
}