Shared code

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

class SgTree{
    vector<pair<int, int>> seg;

    public:

    SgTree(int n, vector<int>&a){
        seg.resize(4*n+1);
        build(0, 0, n-1, a);
    }

    // function to find the building greater than threshold in a given range
    int calcTaller(int idx, int low, int high, int threshold){
        // max of range is less than limit
        if(seg[idx].first<=threshold) return 0;

        if(low==high) return 1;
        int mid = (low+high)>>1;

        // if in left section max is less than limit return for the right section
        if(seg[2*idx+1].first<=threshold) return calcTaller(2*idx+2, mid+1, high, threshold);

        //now there can be some buildings in left also
        int leftCnt = calcTaller(2*idx+1, low, mid, threshold);
        int rightCnt = seg[idx].second - seg[2*idx+1].second;

        return leftCnt+rightCnt;
    }

    void build(int idx, int low, int high, vector<int> &a){
        if(low==high){
            seg[idx] = {a[low], 1};
            return;
        }

        int mid = (low+high)>>1;
        build(2*idx+1, low, mid, a);
        build(2*idx+2, mid+1, high, a);

        int maxHeight = max(seg[2*idx+1].first, seg[2*idx+2].first);

        int leftMax = seg[2*idx+1].first;
        int rightBigger = calcTaller(2*idx+2, mid+1, high, leftMax);        //using the left subtree maxHeight as threshold for right one

        int totalVisible = seg[2*idx+1].second+rightBigger;
        seg[idx] = {maxHeight, totalVisible};
        return;
    }

    int query(int idx, int low, int high, int l, int r, int &maxiHeight){
        // no overlap
        if(r<low or high<l) return 0;

        // complete overlap
        if(l<=low and r>=high) {
            int val = calcTaller(idx, low, high, maxiHeight);
            maxiHeight = max(maxiHeight, seg[idx].first);
            return val;
        }

        int mid = (low+high)>>1;
        int left = query(2*idx+1, low, mid, l, r, maxiHeight);
        int right = query(2*idx+2, mid+1, high, l, r, maxiHeight);

        return left+right;

    }
};

int main(){
    int n; cin>>n;
    int q; cin>>q;

    vector<int> heights(n); for(auto &i: heights) cin>>i;
    SgTree sg(n, heights);

    while(q--){
        int a, b; cin>>a>>b;
        a--, b--;

        int maxiHeight = 0;
        int ans = sg.query(0, 0, n-1, a, b, maxiHeight);
        cout<<ans<<endl;
    }
    
    return 0;
}