Shared code

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll int maxN = 200005;
vector<ll int> arr(maxN,0);
vector<ll int> t[4*maxN];

void build(ll int si,ll int ss, ll int se){
    if(ss==se) t[si].push_back(arr[ss]);
    else{
        ll int mid = (ss+se)/2;
        build(si*2,ss,mid);
        build(si*2+1,mid+1,se);
        ll int l=0,r=0;
        t[si].reserve(t[si*2].size() + t[si*2+1].size());
        while(l<t[si*2].size() && r<t[si*2+1].size()){
            if(t[si*2][l]<=t[si*2+1][r]){
                t[si].push_back(t[si*2][l]);
                l++;
            }else{
                t[si].push_back(t[si*2+1][r]);
                r++;
            }
        }
        while(l<t[si*2].size()){
            t[si].push_back(t[si*2][l]);
            l++;
        }
        while(r<t[si*2+1].size()){
            t[si].push_back(t[si*2+1][r]);
            r++;
        }
        return;
    }
}
ll int query(ll int si,ll int ss, ll int se,ll int qs, ll int qe, ll int c,ll int d){
    if(qs>se || qe<ss) return 0;
    if(ss>=qs && se<=qe){
        ll it = upper_bound(t[si].begin(),t[si].end(),d)-lower_bound(t[si].begin(),t[si].end(),c);
        return it;
    }else{
        ll int mid = (ss+se)/2;
        return query(si*2,ss,mid,qs,qe,c,d)+query(si*2+1,mid+1,se,qs,qe,c,d);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll int n,q;
    cin>>n>>q;
    for(ll int i=1;i<=n;i++) cin>>arr[i];
    build(1,1,n);
    for(ll int i=1;i<=q;i++){
        ll int u,v,c,d;
        cin>>u>>v>>c>>d;
        cout<<query(1,1,n,u,v,c,d)<<endl;
    }
    return 0;
}