Shared code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define PLL pair<long long, long long>
#define LL long long

#define faster {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define all(v) v.begin(),v.end()

const LL mod = 998244353;
const int N = 1e6 + 10;

const LL INF = 1e17 + 1;
const int inf = 1e9 + 1;

void solve(int tc) {
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for(auto &u: a)
        cin >> u;
    
    vector<int> ans(q);
    vector<tuple<int, int, int>> ql[n + 1];
    vector<tuple<int, int, int>> qr[n + 1];

    ordered_set os;

    for(int i = 0; i < q; i++){
        int l, r, x, y; cin >> l >> r >> x >> y;
        ql[l].push_back({x, y, i});
        qr[r].push_back({x, y, i});
    }

    for(int i = 1; i <= n; i++){
        for(auto [x, y, id] : ql[i]){
            ans[id] -= (os.order_of_key(y + 1) - os.order_of_key(x));
        }
        os.insert(a[i - 1]);
        for(auto [x, y, id] : qr[i]){
            ans[id] += (os.order_of_key(y + 1) - os.order_of_key(x));
        }
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << '\n';
    }
}

signed main() {
    faster
    int t = 1;
    // cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        solve(tc);
    }
    return 0;
}