我看了出题人本题的做法，感觉很难写，就自己胡了一个\(O((n + m) \sqrt n)\)的做法。

第一步我的想法与出题人一样，都是考虑容斥降维。对第\(i\)组询问，我们枚举两个事件中较大的一个点\((a, b)\)，它对答案的贡献为:所有满足\(r_{i, 1} \leq x \leq a, c_{i, 1} \leq y \leq b\)且\((x, y) \neq (a, b)\)的点数。把这个贡献按照常见的二维前缀和的方式拆成四种贡献（有些贡献要乘以\(-1\)的系数）：

贡献一:所有满足\(x \leq a, y \leq b, (x, y) \neq (a, b)\)的点数。

贡献二：所有满足\(x < r_{i, 1}, y < c_{i, 1}\)的点数。

贡献三：所有满足\(x < r_{i, 1}, y \leq b\)的点数。

贡献四：所有满足\(x \leq a, y < c_{i, 1}\)的点数。

考虑贡献一只和矩形内的每个点有关，可以用树状数组预处理比每个点“小”的点数再做一次静态二维数点。贡献二**只和\(r_{i, 1}, c_{i, 1}\)有关，可以用两次二维数点解决。由对称性，我们只需要考虑贡献三如何计算（贡献四只需要把\(x, y\)反过来就变成贡献三了）。

贡献三里面对\((a, b)\)有\(r_{i, 1} \leq a \leq r_{i, 2}, c_{i, 1} \leq b \leq c_{i, 2}\)的限制，我们再把\(c_{i, 1} \leq b \leq c_{i, 2}\)这个条件拆成前缀和，于是问题就变成了：

每次询问是一个三元组\((l, r, w)\)，你需要回答满足\((a, b) \leq (c, d)\)，\(a < l \leq c \leq r, b < d \leq w\)的点对数量。

接下来考虑这个三维问题怎么做。我们把\(0, 1, \cdots, n\)中所有\(\lfloor \sqrt{n} \rfloor\)的倍数称为关键点，建立\(O(\sqrt n)\)个关键点。对每个询问\((l, r, w)\)，我们设\(\leq l\)且离\(l\)最近的关键点为\(l'\)，那么考虑将\((l, r, w)\)的\(l\)每次减1移动到\(l'\)的时候，答案的增量都可以用二维数点来计算。

这样，问题变成了\(O(m)\)组\(l\)是关键点的询问和\(O(m \sqrt m)\)组二维数点的询问。后者可以用扫描线 + \(O(\sqrt n)\)修改，\(O(1)\)询问的分块数据结构来解决。而前者可以枚举\(l\)，算出\(x \ge l\)的每个点\((x, y)\)对答案的贡献（这只需要一次前缀和），然后对\(r\)做扫描线，问题又变成了：单点加一个数，询问前缀和。这一问题可以用\(O(1)\)修改，\(O(\sqrt n)\)询问的分块结构来解决。

总结：

1. “容斥降维”在某些问题上比较常用，比如静态询问坐标上一个直角边平行于坐标轴的点数。
2. 本文后半部分的操作实际上是回滚莫队的思想，再结合了lxl提出的莫队二次离线的思想。

代码如下（不要在意我的辣鸡英文水平了）：

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

const int N = 100600, M = 200005, LOG = 25, LIM = 400;

template <class T>
void read(T &x) {
    int sgn = 1;
    char ch;
    x = 0;
    for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
    if (ch == '-') ch = getchar(), sgn = -1;
    for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
    x *= sgn;
}
template <class T>
void write(T x) {
    if (x < 0) putchar('-'), write(-x);
    else if (x < 10) putchar(x + '0');
    else write(x / 10), putchar(x % 10 + '0');
}

//Fenwick tree and persistent segment tree
//num_i denotes the number of integer j such that 1 <= j < i and p_j < p_i

int n, m, lim, p[N], num[N], fenwick[N];
int rt[N], sgt1[N * LOG], lch[N * LOG], rch[N * LOG], cnt = 0;
long long sgt2[N * LOG], ans[M];

//Fenwick tree
int lowbit(int x) {
    return x & -x;
}
void add(int x, int val) {
    for (; x <= n; x += lowbit(x)) fenwick[x] += val;
}
int query(int pos) {
    int res = 0;
    for (; pos; pos ^= lowbit(pos)) res += fenwick[pos];
    return res;
}
void get_num() {
    for (int i = 0; i <= n; i++) fenwick[i] = 0;
    for (int i = 1; i <= n; i++) {
        num[i] = query(p[i]);
        add(p[i], 1);
    }
}
//Persistent segment tree
int newnode() {
    int x = ++cnt;
    sgt1[x] = 0, sgt2[x] = 0ll;
    lch[x] = rch[x] = 0;
    return x;
}
int build(int l, int r) {
    int x = newnode(), mid = l + r >> 1;
    if (l < r) lch[x] = build(l, mid), rch[x] = build(mid + 1, r);
    return x;
}
int insert(int pos, int l, int r, int now, int val1, int val2) {
    int mid = l + r >> 1, x = newnode();
    sgt1[x] = sgt1[now] + val1;
    sgt2[x] = sgt2[now] + val2;
    lch[x] = lch[now], rch[x] = rch[now];
    if (l < r) {
        if (pos <= mid) lch[x] = insert(pos, l, mid, lch[now], val1, val2);
        else rch[x] = insert(pos, mid + 1, r, rch[now], val1, val2);
    }
    return x;
}
int query1(int left, int right, int l, int r, int now) {
    int mid = l + r >> 1;
    if (left > right) return 0;
    if (l == left && r == right) return sgt1[now];
    else if (right <= mid) return query1(left, right, l, mid, lch[now]);
    else if (left > mid) return query1(left, right, mid + 1, r, rch[now]);
    else return query1(left, mid, l, mid, lch[now]) + query1(mid + 1, right, mid + 1, r, rch[now]);
}
long long query2(int left, int right, int l, int r, int now) {
    int mid = l + r >> 1;
    if (left > right) return 0ll;
    if (l == left && r == right) return sgt2[now];
    else if (right <= mid) return query2(left, right, l, mid, lch[now]);
    else if (left > mid) return query2(left, right, mid + 1, r, rch[now]);
    else return query2(left, mid, l, mid, lch[now]) + query2(mid + 1, right, mid + 1, r, rch[now]);
}
void build_tree() {
    rt[0] = build(1, n);
    for (int i = 1; i <= n; i++) {
        rt[i] = insert(p[i], 1, n, rt[i - 1], 1, num[i]);
    }
}

struct qry {
    int id, coef;
    int l, r, w;
} ;
// A data structure called D1
// O(sqrt(n)) modify
// O(1) query
struct D1 {
    int pre1[LIM], pre2[N];
    void init() {
        for (int i = 0; i <= lim; i++) pre1[i] = 0;
        for (int i = 0; i <= n; i++) pre2[i] = 0;
    }
    void add(int pos, int val) {
        for (int i = pos / lim; i <= lim; i++) pre1[i] += val;
        for (int i = pos; i < pos / lim * lim + lim; i++) pre2[i] += val;
    }
    int query(int pos) {
        if (pos / lim) return pre1[pos / lim - 1] + pre2[pos];
        else return pre2[pos];
    }
} DS1;
// A data structure called D2
// O(1) modify
// O(sqrt(n)) query
struct D2 {
    long long vec1[LIM], vec2[N];
    void init() {
        for (int i = 0; i <= lim; i++) vec1[i] = 0ll;
        for (int i = 0; i <= n; i++) vec2[i] = 0ll;
    }
    void add(int pos, int val) {
        vec1[pos / lim] += val;
        vec2[pos] += val;
    }
    long long query(int pos) {
        long long res = 0;
        for (int i = 0; i < pos / lim; i++) res += vec1[i];
        for (int i = pos / lim * lim; i <= pos; i++) res += vec2[i];
        return res;
    }
} DS2;
struct D3 {
    int perm[N], num[N];
    vector<qry> qry1[N], qry2[N];
    void add_qry(qry q) {
        qry1[q.l].push_back(q), qry2[q.r].push_back(q);
    }
    // We proceed the impact of O(sqrt(n)) values in the part.
    // Then we can assume that lim | l or l = n.
    void proceed_small() {
        DS1.init();
        for (int i = 1; i <= n; i++) {
            DS1.add(perm[i], 1);
            for (int j = 0; j < qry2[i].size(); j++) {
                int id = qry2[i][j].id, coef = qry2[i][j].coef;
                int l = qry2[i][j].l, w = qry2[i][j].w;
                for (int i = l / lim * lim; i < l; i++) {
                    if (i && perm[i] <= w) {
                        ans[id] += coef * (DS1.query(w) - DS1.query(perm[i]));
                        ans[id] -= coef * num[i];
                    }
                }
            }
            int ri = min(n, (i / lim + 1) * lim - 1);
            for (int j = i + 1; j <= ri; j++) {
                for (int k = 0; k < qry1[j].size(); k++) {
                    int id = qry1[j][k].id, coef = qry1[j][k].coef;
                    int w = qry1[j][k].w;
                    if (perm[i] <= w) ans[id] -= coef * (DS1.query(w) - DS1.query(perm[i]));
                }
            }
        }
    }

    int tmp[N];
    void proceed_big() {
        for (int i = 0; i < n; i += lim) {
            for (int j = 0; j <= n; j++) tmp[j] = 0;
            for (int j = 1; j < i; j++) tmp[perm[j]]++;
            for (int j = 1; j <= n; j++) tmp[j] += tmp[j - 1];
            DS2.init();
            for (int j = i; j <= n; j++) {
                DS2.add(perm[j], tmp[perm[j]]);
                for (int k = 0; k < qry2[j].size(); k++) {
                    int id = qry2[j][k].id, coef = qry2[j][k].coef;
                    int l = qry2[j][k].l, w = qry2[j][k].w;
                    if (i <= l && l < i + lim) ans[id] += 1ll * coef * DS2.query(w);
                }
            }
        }
    }
} P1, P2;
//P1 and P2 denotes the two different but similar parts of the algorithm.

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(p[i]);
    get_num();
    build_tree();
    //Initialize P1 and P2.
    while (lim * lim <= n) lim++;
    for (int i = 1; i <= n; i++) {
        P1.perm[i] = p[i], P2.perm[p[i]] = i;
        P1.num[i] = num[i], P2.num[p[i]] = num[i];
    }
    for (int i = 0; i <= n; i++) {
        P1.qry1[i].clear(), P1.qry2[i].clear();
        P2.qry1[i].clear(), P2.qry2[i].clear();
    }
    for (int i = 1; i <= m; i++) {
        int lx, rx, ly, ry;
        read(lx), read(rx), read(ly), read(ry);
        // The first part
        // You can avoid persistent segment tree since offline queries are allowed.
        // But as a matter of convenient, I use persistent segment tree.
        ans[i] = query2(ly, ry, 1, n, rt[rx]) - query2(ly, ry, 1, n, rt[lx - 1]);
        int cnt1 = query1(1, ly - 1, 1, n, rt[lx - 1]), cnt2 = query1(ly, ry, 1, n, rt[rx]) - query1(ly, ry, 1, n, rt[lx - 1]);
        ans[i] += 1ll * cnt1 * cnt2;
        // The second part
        // We divide the whole query into four parts.
        // Then we should proceed these 4m queries offline, applying block algorithm.
        qry qry1 = {i, -1, lx, rx, ry}, qry2 = {i, 1, lx, rx, ly - 1};
        qry qry3 = {i, -1, ly, ry, rx}, qry4 = {i, 1, ly, ry, lx - 1};
        P1.add_qry(qry1), P1.add_qry(qry2);
        P2.add_qry(qry3), P2.add_qry(qry4);
    }
    P1.proceed_small(), P1.proceed_big();
    P2.proceed_small(), P2.proceed_big();
    for (int i = 1; i <= m; i++) write(ans[i]), putchar('\n');
    return 0;
}