Hướng dẫn giải của Bedao Mini Contest 16 - SHOOTING
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Nhận thấy, ~2~ phát bắn của Lợi chắc chắn vào đầu mút của các tấm bia.
Do đó ta rời rạc hoá toạ độ về từ ~1~ đến ~2 \times n~ nhằm dễ cài đặt.
Subtask ~1~: ~O(n^3)~.
Ta duyệt trâu qua hai toạ độ và các tấm bia để tìm kết quả tối ưu.
Subtask ~2~:~O(n^3 / 32)~.
Ta chuẩn bị tập hợp các tấm bia chứa toạ độ ~x~ là ~S_x~. Lưu ~S_x~ dưới dạng ~std::bitset~. Khi ta duyệt hai toạ độ ~x, y~, ta dễ dàng tính được phần hợp của ~S_x~ và ~S_y~ trong ~O(\frac{n}{32})~.
Subtask ~3~: ~O(n \times \log(n))~.
Ta duyệt toạ độ nhỏ hơn. Giả sử là ~x~. Giả sử tập hợp đoạn không chứa ~x~ là ~S~. Bài toán trở thành tìm toạ độ tối ưu trong ~x + 1, x + 2, ..., 2 \times n~ mà có nhiều đoạn trong ~S~ chứa nó nhất.
Nếu ta nhìn nhận bài toán trên theo hướng kĩ thuật quét đường thì sẽ thấy đây là một bài cơ bản. Ta duy trì mảng ~a_i~ là số tấm bia chứa toạ độ ~i~ trong khi duyệt tăng dần giá trị ~x~. Khi xét đến ~x~ và tồn tại tấm bia ~[x, x']~. Ta biết chắc rằng: ~a[x..x']~ giảm đi ~1~. Việc đơn giản bây giờ là cập nhật lại mảng ~a~ và lấy ~max(a[(x+1)..(2 \times n)])~.
Do đó mảng ~a~ của ta cần hỗ trợ hai thao tác:
- Giảm các giá trị trong một đoạn
- Lấy giá trị max trong một đoạn.
Vậy ta dùng CTDL Segment tree để tối ưu.
Code mẫu
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 2e5 + 5; struct Segtree { int n; vector<int> tree, lazy; Segtree(int _n) : n(_n) { tree.assign(n * 4 + 5, 0); lazy.assign(n * 4 + 5, 0); } void build(int node, int l, int r, int* sum) { if (l == r) { tree[node] = sum[l]; return; } int mid = (l + r) >> 1; build(node * 2, l, mid, sum); build(node * 2 + 1, mid + 1, r, sum); tree[node] = max(tree[node * 2], tree[node * 2 + 1]); } void build(int* sum) { build(1, 1, n, sum); } void push(int node) { for (int i = node * 2; i <= node * 2 + 1; ++ i) { tree[i] -= lazy[node]; lazy[i] += lazy[node]; } lazy[node] = 0; } void update(int node, int l, int r, int u, int v) { if (l > v || r < u) return; if (l >= u && r <= v) { tree[node] -= 1; lazy[node] += 1; return; } push(node); int mid = (l + r) >> 1; update(node * 2, l, mid, u, v); update(node * 2 + 1, mid + 1, r, u, v); tree[node] = max(tree[node * 2], tree[node * 2 + 1]); } void update(int l, int r) { update(1, 1, n, l, r); } int get(int node, int l, int r, int u, int v) { if (l > v || r < u) return 0; if (l >= u && r <= v) return tree[node]; push(node); int mid = (l + r) >> 1; return max(get(node * 2, l, mid, u, v), get(node * 2 + 1, mid + 1, r, u, v)); } int get(int l, int r) { return get(1, 1, n, l, r); } }; int n; pair<int, int> a[N]; vector<int> pos[N * 2]; int sum[N * 2]; void compress() { vector<int> vt; for (int i = 1; i <= n; ++ i) { auto& [u, v] = a[i]; vt.push_back(u); vt.push_back(v); } sort(vt.begin(), vt.end()); vt.resize(unique(vt.begin(), vt.end()) - vt.begin()); for (int i = 1; i <= n; ++ i) { auto& [u, v] = a[i]; u = upper_bound(vt.begin(), vt.end(), u) - vt.begin(); v = upper_bound(vt.begin(), vt.end(), v) - vt.begin(); } } void solve() { cin >> n; for (int i = 1; i <= n; ++ i) { int x, y; cin >> x >> y; a[i] = {x, y}; } compress(); for (int i = 1; i <= n; ++ i) { auto [u, v] = a[i]; // cout << u << " " << v << endl; pos[u].push_back(v); sum[u] ++; sum[v + 1] --; } int res = 0; for (int i = 1; i <= 2 * n; ++ i) { sum[i] += sum[i - 1]; res = max(res, sum[i]); } Segtree sgt(n * 2); sgt.build(sum); for (int i = 1; i < 2 * n; ++ i) { for (auto j : pos[i]) { sgt.update(i, j); } // cout << i << " " << sum[i] << " " << sgt.get(i + 1, 2 * n) << endl; res = max(res, sum[i] + sgt.get(i + 1, 2 * n)); } cout << res; } main() { cin.tie(0)->sync_with_stdio(0); solve(); }
Bình luận