Given $n$ points $(x_i, y_i)$ and $m$ rectangles, determine the number of points inside each rectangle.

Solution Approach

The problem requires counting points satisfying $l_j \le x_i \le r_j$ and $d_j \le y_i \le u_j$. By applying inclusion-exclusion, the count for a rectangle can be expressed as:

$$ \begin{aligned} \text{count} = &, Q(r_j, u_j) \ &- Q(l_j-1, u_j) \ &- Q(r_j, d_j-1) \ &+ Q(l_j-1, d_j-1) \end{aligned} $$

where $Q(a, b)$ counts points with $x_i \le a$ and $y_i \le b$.

To compute this offline, process events in increasing order of $y$-coordinate. For each point $(x_i, y_i)$, generate an insertion event at $y_i$. For each query boundary, generate a query event at the respective $y$-coordinate. Use a Fenwick tree to manage $x$-coordinates, updating and querying prefix sums.

Implementation

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

typedef long long ll;
const int MAXN = 500010;

struct Point { int x_coord, y_coord; };

struct Event {
    int y_val, x_val, multiplier, query_id;
    bool operator<(const Event& other) const { return y_val < other.y_val; }
};

class FenwTree {
    vector<int> tree;
    int size;
public:
    FenwTree(int n) : size(n), tree(n + 1, 0) {}
    void modify(int idx, int delta) {
        for (; idx <= size; idx += idx & -idx)
            tree[idx] += delta;
    }
    int prefix_sum(int idx) {
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx)
            sum += tree[idx];
        return sum;
    }
};

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

    int num_points, num_queries;
    cin >> num_points >> num_queries;
    vector<Point> points(num_points);
    vector<int> x_vals;
    for (int i = 0; i < num_points; i++) {
        cin >> points[i].x_coord >> points[i].y_coord;
        x_vals.push_back(points[i].x_coord);
    }

    vector<Event> events;
    for (int i = 0; i < num_points; i++)
        events.push_back({points[i].y_coord, points[i].x_coord, 0, -1});

    for (int i = 0; i < num_queries; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        events.push_back({y2, x2, 1, i});
        events.push_back({y2, x1 - 1, -1, i});
        events.push_back({y1 - 1, x2, -1, i});
        events.push_back({y1 - 1, x1 - 1, 1, i});
    }

    sort(x_vals.begin(), x_vals.end());
    x_vals.erase(unique(x_vals.begin(), x_vals.end()), x_vals.end());
    int distinct_count = x_vals.size();

    auto get_index = [&](int val) {
        return lower_bound(x_vals.begin(), x_vals.end(), val) - x_vals.begin() + 1;
    };

    sort(events.begin(), events.end());
    FenwTree fenw(distinct_count);
    vector<int> results(num_queries, 0);

    for (auto& evt : events) {
        if (evt.multiplier == 0) {
            int pos = get_index(evt.x_val);
            fenw.modify(pos, 1);
        } else {
            int pos = upper_bound(x_vals.begin(), x_vals.end(), evt.x_val) - x_vals.begin();
            int res = fenw.prefix_sum(pos);
            results[evt.query_id] += evt.multiplier * res;
        }
    }

    for (int i = 0; i < num_queries; i++)
        cout << results[i] << '\n';

    return 0;
}

Application: Sum of Distinct Values in Intervals

Consider an array $a$ of length $n$. For each query $[l, r]$, compute the sum of distinct values in the subarray. Define $prev[i]$ as the last occurrence index of $a_i$ (or 0 if none). The contribution of $a_i$ is counted if $prev[i] < l$ and $l \le i \le r$. This transforms into a 2D point counting problem: points $(i, prev[i])$ and queries $(l \le i \le r, prev[i] < l)$.

Implementation

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

typedef long long ll;
const int MAXN = 500010;

struct Event {
    int key, value, id, type;
    bool operator<(const Event& other) const { return key < other.key; }
};

class FenwTree {
    vector<ll> tree;
    int size;
public:
    FenwTree(int n) : size(n), tree(n + 1, 0) {}
    void adjust(int idx, ll delta) {
        for (; idx <= size; idx += idx & -idx)
            tree[idx] += delta;
    }
    ll range_sum(int idx) {
        ll sum = 0;
        for (; idx > 0; idx -= idx & -idx)
            sum += tree[idx];
        return sum;
    }
};

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

    int arr_size, query_count;
    cin >> arr_size >> query_count;
    vector<int> arr(arr_size + 1), prev_occur(arr_size + 1, 0);
    vector<int> last_pos(1000001, 0);

    for (int i = 1; i <= arr_size; i++) {
        cin >> arr[i];
        prev_occur[i] = last_pos[arr[i]];
        last_pos[arr[i]] = i;
    }

    vector<Event> events;
    for (int i = 1; i <= arr_size; i++)
        events.push_back({prev_occur[i], arr[i], i, 0});

    for (int i = 0; i < query_count; i++) {
        int left, right;
        cin >> left >> right;
        events.push_back({right, 0, i, 1});
        events.push_back({left - 1, 0, i, -1});
    }

    sort(events.begin(), events.end());
    FenwTree fenw(arr_size);
    vector<ll> answers(query_count, 0);

    for (auto& evt : events) {
        if (evt.type == 0) {
            fenw.adjust(evt.id, evt.value);
        } else {
            ll res = fenw.range_sum(evt.key);
            answers[evt.id] += evt.type * res;
        }
    }

    for (int i = 0; i < query_count; i++)
        cout << answers[i] << '\n';

    return 0;
}

Application: Range Minimum Query

Find the minimum value in subarray $[l, r]$. Represent each element $a_i$ as point $(i, a_i)$. Process events sorted by value, using a segment tree to track minimum values in active ranges.

Implementation

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

const int MAXN = 200010;
const int INF = 0x3f3f3f3f;

struct Event {
    int key, type, pos, r, id;
    bool operator<(const Event& other) const { return key < other.key; }
};

class SegTree {
    vector<int> min_val;
    int n;
    void build(int node, int l, int r) {
        if (l == r) {
            min_val[node] = INF;
            return;
        }
        int mid = (l + r) >> 1;
        build(node << 1, l, mid);
        build(node << 1 | 1, mid + 1, r);
        min_val[node] = min(min_val[node << 1], min_val[node << 1 | 1]);
    }
    void update(int node, int l, int r, int idx, int val) {
        if (l == r) {
            min_val[node] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (idx <= mid) update(node << 1, l, mid, idx, val);
        else update(node << 1 | 1, mid + 1, r, idx, val);
        min_val[node] = min(min_val[node << 1], min_val[node << 1 | 1]);
    }
    int query(int node, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return INF;
        if (ql <= l && r <= qr) return min_val[node];
        int mid = (l + r) >> 1;
        return min(query(node << 1, l, mid, ql, qr),
                   query(node << 1 | 1, mid + 1, r, ql, qr));
    }
public:
    SegTree(int sz) : n(sz) {
        min_val.resize(4 * sz);
        build(1, 1, n);
    }
    void assign(int idx, int val) { update(1, 1, n, idx, val); }
    int range_min(int l, int r) { return query(1, 1, n, l, r); }
};

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

    int arr_size, query_count;
    cin >> arr_size >> query_count;
    vector<int> arr(arr_size + 1);
    vector<Event> events;

    for (int i = 1; i <= arr_size; i++) {
        cin >> arr[i];
        events.push_back({arr[i], 0, i, 0, 0});
    }

    for (int i = 1; i <= query_count; i++) {
        int l, r;
        cin >> l >> r;
        events.push_back({0, 1, l, r, i});
    }

    sort(events.begin(), events.end());
    SegTree seg_tree(arr_size);
    vector<int> answers(query_count + 1, -1);

    for (auto& evt : events) {
        if (evt.type == 0) {
            seg_tree.assign(evt.pos, evt.key);
        } else {
            int res = seg_tree.range_min(evt.pos, evt.r);
            answers[evt.id] = (res == INF) ? -1 : res;
        }
    }

    for (int i = 1; i <= query_count; i++)
        cout << answers[i] << '\n';

    return 0;
}