Hướng giải của Truy Vấn Bao Phủ Hoàn Toàn
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.
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ả:
Hướng dẫn giải: Truy Vấn Bao Phủ Hoàn Toàn
Phân tích bài toán
Yêu cầu tìm tất cả các đoạn thẳng bao phủ hoàn toàn \([A, B]\), tức là \(L_i \le A \le B \le R_i\). Đây là bài toán truy vấn 2D trên mảng tĩnh: \(L_i \le A\) và \(R_i \ge B\). Ta xử lý offline bằng cách sắp xếp các đoạn thẳng theo đầu mút trái \(L_i\) tăng dần, các truy vấn theo giới hạn trái \(A\) tăng dần:
- Duy trì 2 cây Segment Tree (một cây lưu đếm số lượng, một cây lưu checksum tổng tích \(L_i \times R_i \pmod{MOD}\)). Các vị trí trong cây Segment Tree ứng với đầu mút phải \(R_i\) đã được nén.
- Khi xử lý truy vấn có giới hạn trái là \(A\), ta chèn mọi đoạn thẳng thỏa mãn \(L_i \le A\) vào Segment Tree tại vị trí đầu mút phải \(R_i\) của nó.
- Sau đó, ta truy vấn tìm tổng trên Segment Tree ở khoảng chỉ số tương ứng với \([B, +\infty]\). Các đoạn thẳng tại vùng này đảm bảo có mút phải \(R_i \ge B\).
Độ phức tạp
- Thời gian: \(O((N + Q) \log(N + Q))\) thời gian chạy.
- Không gian: \(O(N + Q)\) bộ nhớ.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
struct Interval {
int l, r;
bool operator<(const Interval& other) const {
return l < other.l;
}
};
struct Query {
int a, b, id;
bool operator<(const Query& other) const {
return a < other.a;
}
};
vector<long long> tree_count;
vector<long long> tree_sum;
int sz;
void update(int id, int lo, int hi, int pos, int cnt_diff, long long sum_diff) {
if (lo == hi) {
tree_count[id] += cnt_diff;
tree_sum[id] = (tree_sum[id] + sum_diff) % MOD;
if (tree_sum[id] < 0) tree_sum[id] += MOD;
return;
}
int mid = lo + (hi - lo) / 2;
if (pos <= mid) update(2 * id, lo, mid, pos, cnt_diff, sum_diff);
else update(2 * id + 1, mid + 1, hi, pos, cnt_diff, sum_diff);
tree_count[id] = tree_count[2 * id] + tree_count[2 * id + 1];
tree_sum[id] = (tree_sum[2 * id] + tree_sum[2 * id + 1]) % MOD;
}
pair<long long, long long> query_st(int id, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return {0, 0};
if (l <= lo && hi <= r) return {tree_count[id], tree_sum[id]};
int mid = lo + (hi - lo) / 2;
auto left_res = query_st(2 * id, lo, mid, l, r);
auto right_res = query_st(2 * id + 1, mid + 1, hi, l, r);
return {left_res.first + right_res.first, (left_res.second + right_res.second) % MOD};
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
if (!(cin >> n >> q)) return 0;
vector<Interval> intervals(n);
vector<int> coords;
for (int i = 0; i < n; i++) {
cin >> intervals[i].l >> intervals[i].r;
coords.push_back(intervals[i].r);
}
vector<Query> queries(q);
for (int i = 0; i < q; i++) {
cin >> queries[i].a >> queries[i].b;
queries[i].id = i;
coords.push_back(queries[i].b);
}
sort(coords.begin(), coords.end());
coords.erase(unique(coords.begin(), coords.end()), coords.end());
auto get_pos = [&](int val) {
return lower_bound(coords.begin(), coords.end(), val) - coords.begin();
};
sz = coords.size();
tree_count.assign(4 * sz, 0);
tree_sum.assign(4 * sz, 0);
sort(intervals.begin(), intervals.end());
sort(queries.begin(), queries.end());
vector<pair<long long, long long>> ans(q);
int ptr = 0;
for (int i = 0; i < q; i++) {
while (ptr < n && intervals[ptr].l <= queries[i].a) {
int pos = get_pos(intervals[ptr].r);
long long term = (1LL * (intervals[ptr].l % MOD + MOD) % MOD * ((intervals[ptr].r % MOD + MOD) % MOD)) % MOD;
update(1, 0, sz - 1, pos, 1, term);
ptr++;
}
int pos_b = get_pos(queries[i].b);
auto res = query_st(1, 0, sz - 1, pos_b, sz - 1);
ans[queries[i].id] = res;
}
for (int i = 0; i < q; i++) {
cout << ans[i].first << " " << ans[i].second << "\n";
}
return 0;
}
Nhận xét