Segment Tree Basics

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

const int maxN = 100010;
int n;
int64_t t[4 * maxN];
pair<int,int> minimum[4 * maxN];
pair<int,int> maximum[4 * maxN];
int ans = -1;

pair<int,int> combine (pair<int,int> a,pair<int,int> b) {
    if (a.first < b.first) return a;
    if (b.first < a.first) return b;
    return make_pair(a.first,b.second + a.second);
}

pair<int,int> combine_maximum(pair<int,int> a,pair<int,int> b) {
    if (a.first > b.first) return a;
    if (b.first > a.first) return b;
    return make_pair(a.first,a.second + b.second);
}

void build (int64_t a[],int v,int tl,int tr) {
    if (tl == tr) {
        t[v] = a[tl];
        minimum[v] = make_pair(a[tl],1);
        maximum[v] = make_pair(a[tl],1);
    } else {
        int tm = tl + (tr - tl) / 2;
        build(a,v * 2,tl,tm);
        build(a,v * 2 + 1,tm + 1,tr);
        t[v] = t[v * 2] + t[v * 2 + 1];
        minimum[v] = combine(minimum[2 * v],minimum[2 * v + 1]);
        maximum[v] = combine_maximum(maximum[2 * v],maximum[2 * v + 1]);
    }
}

void point_update (int v,int tl,int tr,int pos,int new_val) {
    if (tl == tr) {
        t[v] = new_val;
        minimum[v] = make_pair(new_val,1);
        maximum[v] = make_pair(new_val,1);
    } else {
        int tm = tl + (tr - tl) / 2;
        if (pos <= tm) {
            point_update(v * 2,tl,tm,pos,new_val);
        } else {
            point_update(v * 2 + 1,tm + 1,tr,pos,new_val);
        }
        t[v] = t[v * 2] + t[v * 2 + 1];
        minimum[v] = combine(minimum[v * 2],minimum[v * 2 + 1]);
        maximum[v] = combine_maximum(maximum[2 * v],maximum[2 * v + 1]);
    }
}

int64_t sum_query (int v,int tl,int tr,int l,int r) {
    if (l > r) return 0;
    if (l == tl and r == tr) return t[v];
    int tm = tl + (tr - tl) / 2;
    return sum_query(v * 2,tl,tm,l,min(r,tm)) + sum_query(v * 2 + 1,tm + 1,tr,max(l,tm + 1),r);
}

pair<int,int> minimum_query (int v,int tl,int tr,int l,int r) {
    if (l > r) return make_pair(INT_MAX,0);
    if (l == tl and r == tr) return minimum[v];
    int tm = tl + (tr - tl) / 2;
    return combine(minimum_query(v * 2,tl,tm,l,min(r,tm)),minimum_query(v * 2 + 1,tm + 1,tr,max(l,tm + 1),r));
}

pair<int,int> maximum_query (int v,int tl,int tr,int l,int r) {
    if (l > r) return make_pair(INT_MIN,0);
    if (l == tl and r == tr) return maximum[v];
    int tm = tl + (tr - tl) / 2;
    return combine_maximum(maximum_query(v * 2,tl,tm,l,min(r,tm)),maximum_query(v * 2 + 1,tm + 1,tr,max(l,tm + 1),r));
}

int find_kth_one_idx_query (int v,int tl,int tr,int k) {
    if (k > t[v]) return -1; //if input[] contains less then k ones
    if (tl == tr) return tl;
    int tm = tl + (tr - tl) / 2;
    if (k < t[v * 2]) {
        return find_kth_one_idx_query(2 * v,tl,tm,k);
    } else {
        return find_kth_one_idx_query(2 * v + 1,tm + 1,tr,k - t[2 * v]);
    }
}

int find_kth_idx (int v,int tl,int tr,int k) {
    if (tl == tr) return tl;
    int tm = tl + (tr - tl) / 2;
    if (maximum[2 * v].first < k) {
        return find_kth_idx(2 * v + 1,tm + 1,tr,k);
    } else {
        return find_kth_idx(2 * v,tl,tm,k);
    }
}

void find_kth_idx_greater_equal_to_given_idx (int v,int tl,int tr,int k,int l) {
    if (maximum[v].first < k) return;
    if (ans >= 0 or tr < l) return;
    if (tl == tr) {
        if (maximum[v].first >= k) ans = tl;
        return;
    }
    int tm = tl + (tr - tl) / 2;
    find_kth_idx_greater_equal_to_given_idx(v * 2,tl,tm,k,l);
    find_kth_idx_greater_equal_to_given_idx(v * 2 + 1,tm + 1,tr,k,l);
}

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 q;
         cin >> n >> q;
         int64_t input[n];
         for (int i = 0; i < n; ++i) cin >> input[i];
         build(input,1,0,n - 1);
         //for sum_query sum_query (1,0,n - 1,l,r)

         //for minimum / maximum query pair<int,int> res = minimum / maximum_query(1,0,n - 1,l,r);

         //res.first -> min on the given segement and res.second -> count of min/max on a given segment

         //to find kth one find_kth_one_idx_query(1,0,n - 1,k)

         //to find kth idx where input[idx] >= x -> find_kth_idx(1,0,n - 1,x)

         //to find kth idx where idx >= l and input[idx] >= x -> find_kth_idx_greater_equal_to_given_idx(1,0,n - 1,k,l)
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}