Shared code

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
// using merger sort tree algo (MO's algo) -> storing subarray at each node range

class SegTree{
    vector<vector<int>> seg;

    public:
    // constructer
    SegTree(int n, vector<int> &a){
        seg.resize(4*n);
        build(0, 0, n-1, a);
    }

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

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

        int parentSize = seg[2*idx+1].size()+seg[2*idx+2].size();
        seg[idx].resize(parentSize);

        //merge the nodes in linear time in sorted order
        merge(seg[2*idx+1].begin(), seg[2*idx+1].end(), seg[2*idx+2].begin(), seg[2*idx+2].end(), seg[idx].begin());
        return;
    }

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

        // complete overlap
        if(l<=low and high<=r){
            if (seg[idx].back() < c or seg[idx].front() > d) return 0;
            if (seg[idx].front() >= c && seg[idx].back() <= d) return seg[idx].size();

            auto less_than_c = lower_bound(seg[idx].begin(), seg[idx].end(), c);
            auto lessEqual_d = upper_bound(seg[idx].begin(), seg[idx].end(), d);
            int ans = (lessEqual_d - less_than_c);
            return ans;
        }
        
        int mid = (low+high)>>1;
        int left = query(2*idx+1, low, mid, l, r, c, d);
        int right = query(2*idx+2, mid+1, high, l, r, c, d);
        return left+right;
    }
};

int main(){
    //input/output sync
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q; cin>>n>>q;
    vector<int> arr(n); for(auto &i: arr) cin>>i;

    SegTree sg(n, arr);

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

        int ans = sg.query(0, 0, n-1, a, b, c, d);
        cout<<ans<<'\n';
    }
    
    return 0;
}