2250. Count Number of Rectangles Containing Each Point

You are given a 2D integer array rectangles where rectangles[i] = [li, hi] indicates that ith rectangle has a length of li and a height of hi. You are also given a 2D integer array points where points[j] = [xj, yj] is a point with coordinates (xj, yj).

The ith rectangle has its bottom-left corner point at the coordinates (0, 0) and its top-right corner point at (li, hi).

Return an integer array count of length points.length where count[j] is the number of rectangles that contain the jth point.

The ith rectangle contains the jth point if 0 <= xj <= li and 0 <= yj <= hi. Note that points that lie on the edges of a rectangle are also considered to be contained by that rectangle.

#define all(a) begin(a), end(a)
using namespace std;
struct Seg{
    Seg* l = NULL, *r = NULL;
    int mi, ma, c = 0;
    Seg(int l, int r) : mi(l), ma(r) {};

    void update(int n) {
        if(mi > n or ma < n) return;
        c++;
        if(l) l->update(n);
        if(r) r->update(n);
    }

    int qry(int lo, int hi) {
        if(mi > hi or ma < lo) return 0;
        if(lo <= mi and ma <= hi) return c;
        return (l ? l->qry(lo,hi) : 0) + (r ? r->qry(lo,hi) : 0);
    }
};
class Solution {
    Seg* s;
    int init(vector<vector<int>>& r) {
        int n = r.size();
        unordered_set<int> us;
        for(auto& R : r) {
            us.insert(R[1]);
        }
        vector<int> st(begin(us), end(us));
        sort(all(st));
        s = build(st, 0, st.size() - 1);
        return st.back();
    }

    Seg* build(vector<int>& A, int l, int r) {
        if(l > r) return NULL;
        Seg* sg = new Seg(A[l], A[r]);
        if(l == r) return sg;
        int m = l + (r - l) / 2;
        sg->l = build(A, l, m);
        sg->r = build(A, m + 1, r);
        return sg;
    }
public:
    vector<int> countRectangles(vector<vector<int>>& r, vector<vector<int>>& po) {
        int n = r.size(), m = po.size();
        vector<array<int,3>> p;
        vector<int> res(m,0);
        
        for(int i = 0; i < m; i++) {
            p.push_back({po[i][0],po[i][1],i});
        }
        
        sort(all(r));
        sort(all(p));
        
        int ma = init(r);
        int i = n - 1, j = m - 1;

        while(i >= 0 and j >= 0) {
            int lo = r[i][0];
            while(j >= 0 and p[j][0] > lo) j--;

            while(i >= 0 and r[i][0] == lo)
                s->update(r[i--][1]);

            lo = i >= 0 ? r[i][0] : 0;

            while(j >= 0 and p[j][0] > lo) {
                auto [x, y, idx] = p[j--];
                res[idx] = s->qry(y, ma);
            }
        }
        return res;
    }
};