Hướng giải của Ngôi Sao Trên Bầu Trời

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Không gian tọa độ của bầu trời rất lớn (\(10^9 \times 10^9\)) nhưng số lượng truy vấn \(Q\) lại nhỏ (\(Q \le 1000\)). Điều này gợi ý kỹ thuật Rời rạc hóa tọa độ (Coordinate Compression):

  1. Thu thập tất cả các tọa độ \(x\) và \(y\) xuất hiện trong mọi sự kiện của đầu vào.
  2. Sắp xếp và loại bỏ các tọa độ trùng lặp.
  3. Rời rạc hóa các giá trị \(x\) và \(y\) ban đầu về các chỉ số nguyên bé bắt đầu từ \(1\) đến tối đa là \(2Q\).
  4. Sử dụng một mảng BIT 2D có kích thước tương ứng để thực hiện cập nhật điểm và truy vấn tổng hình chữ nhật bình thường.

Mã nguồn C++ mẫu

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

struct Query {
    int t; int x1, y1, x2, y2;
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int q; if (!(cin >> q)) return 0;
    vector<Query> queries(q);
    vector<int> xs, ys;
    for (int i = 0; i < q; i++) {
        cin >> queries[i].t;
        if (queries[i].t == 1) {
            cin >> queries[i].x1 >> queries[i].y1;
            xs.push_back(queries[i].x1);
            ys.push_back(queries[i].y1);
        } else {
            cin >> queries[i].x1 >> queries[i].y1 >> queries[i].x2 >> queries[i].y2;
            xs.push_back(queries[i].x1);
            xs.push_back(queries[i].x2);
            ys.push_back(queries[i].y1);
            ys.push_back(queries[i].y2);
        }
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());

    auto get_x = [&](int x) { return lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1; };
    auto get_y = [&](int y) { return lower_bound(ys.begin(), ys.end(), y) - ys.begin() + 1; };

    int n = xs.size();
    int m = ys.size();
    vector<vector<int>> bit(n + 2, vector<int>(m + 2, 0));

    auto update = [&](int x, int y, int val) {
        for (int i = x; i <= n; i += i & -i) {
            for (int j = y; j <= m; j += j & -j) {
                bit[i][j] += val;
            }
        }
    };

    auto query = [&](int x, int y) {
        int s = 0;
        for (int i = x; i > 0; i -= i & -i) {
            for (int j = y; j > 0; j -= j & -j) {
                s += bit[i][j];
            }
        }
        return s;
    };

    for (int i = 0; i < q; i++) {
        if (queries[i].t == 1) {
            update(get_x(queries[i].x1), get_y(queries[i].y1), 1);
        } else {
            int x1 = get_x(queries[i].x1);
            int y1 = get_y(queries[i].y1);
            int x2 = get_x(queries[i].x2);
            int y2 = get_y(queries[i].y2);
            cout << query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1) << "\n";
        }
    }
}

Nhận xét

Không có ý kiến tại thời điểm này.