Shared code

/**
 *    author: Saurav
 *    created: 2025.05.01 05:23:43
 *    We stop at Candidate Master in 2025
 **/

/* includes and all */

#include<bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(x) cout<<"errr----  "<< #x <<" " <<x<<endl 
#define print(v) do { \
                    cout << "vect--" << #v << " = [ "; \
                    for (int i = 0; i < v.size(); i++) { \
                        cout << v[i] << " "; \
                    } \
                    cout << " ]" << endl; \
                } while(0)
#define print2d(v) do { \
                    cout << "vect-- starts" << endl; \
                    for (int i = 0; i < v.size(); i++) { \
                        cout << "[" << " "; \
                        for (int j = 0; j < v[i].size(); j++) { \
                            cout << v[i][j] << " "; \
                        } \
                        cout << "]" << endl; \
                    } \
                    cout << "vect-- ends" << endl; \
                } while(0)
#define printmap(m) do { \
                    cout << "map-- starts" << endl; \
                    for (auto it = m.begin(); it != m.end(); ++it) { \
                        cout << it->first << " -> " << it->second << endl; \
                    } \
                    cout << "map-- ends" << endl; \
                } while(0)

#define printset(s) do { \
    cout << "set-- starts" << endl; \
    for (auto it = s.begin(); it != s.end(); ++it) { \
        cout << *it << endl; \
    } \
    cout << "set-- ends" << endl; \
} while(0)

#define printpp(v) do { \
                    cout << "vect--" << " = [ "; \
                    for (int i = 0; i < v.size(); i++) { \
                        cout << "(" << v[i].first << ", " << v[i].second << ") "; \
                    } \
                    cout << " ]" << endl; \
                } while(0)
#else
#define debug(x)
#define print(v)
#define print2d(v)
#define printmap(m)
#define printpp(v)
#endif
#define endl "\n"
#define MOD 1000000007
#define mod_add(a, b) (((a) % MOD + (b) % MOD) % MOD)
#define mod_sub(a, b) ((((a) % MOD - (b) % MOD) + MOD) % MOD)
#define mod_mul(a, b) (((1LL * (a) % MOD) * (b) % MOD) % MOD)
#define int long long int
#define mn(a,b,c) min(a,min(b,c))
#define mx(a,b,c) max(a,max(b,c))
#define pp pair<int,int>
using namespace std;

/* write core logic here */
class SegmentTree {
private:
    int n;
    vector<vector<int>> tree;
    vector<int> data;

    // Function to build the segment tree
    void build(int node, int start, int end) {
        if (start == end) {
            // Leaf node will have a single element
            tree[node].push_back(data[start]);
            return;
        }

        int mid = start + (end - start) / 2;
        int left_child = 2 * node + 1;
        int right_child = 2 * node + 2;

        // Recursively build the left and right children
        build(left_child, start, mid);
        build(right_child, mid + 1, end);

        // Merge the sorted vectors from left and right children
        mergeVectors(tree[left_child], tree[right_child], tree[node]);
    }

    // Helper function to merge two sorted vectors
    void mergeVectors(const vector<int> &left, const vector<int> &right, vector<int> &merged) {
        merged.resize(left.size() + right.size());
        int i = 0, j = 0, k = 0;

        while (i < left.size() && j < right.size()) {
            if (left[i] <= right[j]) {
                merged[k++] = left[i++];
            }
            else {
                merged[k++] = right[j++];
            }
        }

        // Copy remaining elements
        while (i < left.size()) {
            merged[k++] = left[i++];
        }
        while (j < right.size()) {
            merged[k++] = right[j++];
        }
    }

    // Function to perform the query
    int queryUtil(int node, int start, int end, int L, int R, int X) const {
        if (R < start || end < L) {
            // No overlap
            return 0;
        }

        if (L <= start && end <= R) {
            // Total overlap
            // Use binary search to find the count of X in tree[node]
            int left_idx = upper_bound(tree[node].begin(), tree[node].end(), X) - tree[node].begin();
            return left_idx;
            
        }

        // Partial overlap
        int mid = start + (end - start) / 2;
        int left_child = 2 * node + 1;
        int right_child = 2 * node + 2;

        int count_left = queryUtil(left_child, start, mid, L, R, X);
        int count_right = queryUtil(right_child, mid + 1, end, L, R, X);

        return count_left + count_right;
    }

public:
    // Constructor to initialize and build the segment tree
    SegmentTree(const vector<int> &input_data) {
        data = input_data;
        n = data.size();
        // Allocate enough space for the segment tree
        tree.resize(4 * n);
        build(0, 0, n - 1);
    }

    // Function to query the frequency of X in range [L, R]
    int query(int L, int R, int X) const {
        if (L < 0 || R >= n || L > R) {
            throw invalid_argument("Invalid query range.");
        }
        return queryUtil(0, 0, n - 1, L, R, X);
    }
};
void solve(){
    int n,q;
    cin>>n>>q;
    vector<int> a(n);
    for(int i = 0; i<n; i++){
        cin>>a[i];
    }

    SegmentTree st(a);
    for(int i = 0; i<q; i++){
        int l,r,x1,x2;
        cin>>l>>r>>x1>>x2;
        l--;
        r--;
        int ans1 = st.query(l,r,x2);
        int ans2 = st.query(l,r,x1-1);
        cout<<ans1 - ans2<<endl;
    }
}
/* logic ends */

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("Error.txt" , "w" , stderr);
    #endif
    int t;
    //cin>>t;
    t = 1;
    while(t--){
        solve();
    }
return 0;
}