Chúng ta không thể xây ma trận 2D kích thước \(m \times n\) vì quá lớn, nên chỉ lưu danh sách p tọa độ cây và áp dụng kỹ thuật quét theo hàng kết hợp với Fenwick Tree 1D trên cột và inclusion-exclusion.

1. Nhận diện khó khăn khi dùng ma trận 2D

• Ma trận kích thước \(m \times n\) có thể lên đến \(10^6 \times 10^6\), tức \(10^{12}\) ô, không thể lưu hay thao tác với prefix-sum 2D do giới hạn bộ nhớ.
• Tuy nhiên, số cây \(p\) tối đa chỉ \(10^5\), nên chỉ cần lưu danh sách tọa độ các cây.

2. Giảm bài toán 2D xuống 1D và quét hàng

• Xét dãy các hàng từ \(1\) đến \(m\) theo thứ tự tăng dần (sweep line).
• Khi quét đến hàng \(r\), cập nhật Fenwick Tree để đánh dấu các cây có hàng nhỏ hơn hoặc bằng r.
• Nhờ đó khi cần biết có bao nhiêu cây trong một khoảng cột nào đó, chỉ việc hỏi Fenwick Tree.

3. Chuyển truy vấn thành hai sự kiện (Inclusion-Exclusion)

Với mỗi truy vấn hình chữ nhật từ \((x, y)\) đến \((z, t)\):

• Tạo sự kiện tại hàng \(z\) với hệ số \(+1\) để đếm số cây có hàng \(\le z\) và cột trong \([y, t]\).
• Tạo sự kiện tại hàng \(x-1\) với hệ số \(-1\) để đếm số cây có hàng \(\le x-1\) và cột trong \([y, t]\).

Kết quả cần tìm chính là \(A(z) - A(x-1)\), trong đó \(A(h)\) là số cây có hàng \(\le h\) và cột trong \([y, t]\).

4. Fenwick Tree trên cột

• Dùng Fenwick Tree (Binary Indexed Tree) kích thước \(n\) để:
  • Cập nhật một cây tại cột \(c\) (point update).
  • Truy vấn prefix-sum từ \(1\) đến \(C\) để đếm số cây trong \([1, C]\).
• Để đếm số cây trong khoảng cột \([y, t]\), ta tính \(sum(1, t) - sum(1, y-1)\).

5. Thuật toán tổng quát

1. Đọc p tọa độ cây vào vector points.
2. Đọc q truy vấn, với mỗi truy vấn (x, y, z, t) tạo hai Event:
   • { row = z, y, t, idx, coef = +1 }
   • { row = x - 1, y, t, idx, coef = -1 }
3. Sắp xếp vector points theo hàng tăng dần; sắp xếp events theo trường row tăng dần.
4. Khởi tạo Fenwick Tree kích thước n.
5. Duyệt lần lượt các event:
   • Trong khi có cây points[pi] với hàng ≤ event.row, cập nhật Fenwick: update(points[pi].col, +1) và tăng pi.
   • Truy vấn Fenwick để lấy số cây trong khoảng cột [y, t], nhân với coef, cộng vào ans[idx].
6. In kết quả ans[i] theo thứ tự truy vấn ban đầu.

6. Độ phức tạp

• Sắp xếp cây: \(O(p \log p)\)
• Sắp xếp sự kiện: \(O((2q) \log(2q)) ≈ O(q \log q)\)
• Fenwick Tree: mỗi cây cập nhật 1 lần, mỗi event truy vấn 1 lần, tổng \(O((p + 2q) \log n)\)
• Tổng cộng: \(O((p + q) \log max(m, n))\), phù hợp với \(p, q \le 10^5\) và \(m, n \le 10^6\).

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

struct BIT {
    int n;
    vector<int> bit;
    BIT(int _n): n(_n), bit(n+1, 0) {}

    // add value v at index i
    void update(int i, int v) {
        for (; i <= n; i += i & -i)
            bit[i] += v;
    }

    // sum of [1..i]
    int query(int i) const {
        int s = 0;
        for (; i > 0; i -= i & -i)
            s += bit[i];
        return s;
    }

    // sum of [l..r]
    int rangeQuery(int l, int r) const {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

struct Event {
    int row;
    int y, t;
    int idx;
    int coef;  // +1 or -1
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n, p, q;
    cin >> m >> n >> p >> q;

    vector<pair<int,int>> points(p);
    for(int i = 0; i < p; i++){
        cin >> points[i].first >> points[i].second;
    }

    // Build two events per query:
    // count up to row z with +1, and up to row x-1 with -1
    vector<Event> events;
    events.reserve(2*q);
    vector<ll> ans(q, 0);

    for(int i = 0; i < q; i++){
        int x, y, z, t;
        cin >> x >> y >> z >> t;
        events.push_back({ z,   y, t, i, +1 });
        events.push_back({ x-1, y, t, i, -1 });
    }

    // Sort points by row, and events by row
    sort(points.begin(), points.end(),[](auto &a, auto &b){ return a.first < b.first; });
    sort(events.begin(), events.end(),[](auto &a, auto &b){ return a.row < b.row; });

    // Fenwick tree over columns [1..n]
    BIT bit(n);

    int pi = 0;
    for(const auto &e : events){
        // Add all points with row <= e.row to the BIT
        while(pi < p && points[pi].first <= e.row){
            bit.update(points[pi].second, 1);
            pi++;
        }
        // Query how many of those points lie in columns [y..t]
        int cnt = bit.rangeQuery(e.y, e.t);
        ans[e.idx] += ll(e.coef) * cnt;
    }

    for(int i = 0; i < q; i++) cout << ans[i] << "\n";
    return 0;
}