Hướng dẫn cho LQDOJ CUP 2022 - Round 4 - COWBOY

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Flower_On_Stone

Subtask \(1\) (\(30\%\) số điểm): \(x_1 = x_2 = \ldots = x_n\) hoặc \(y_1 = y_2 = \ldots = y_n\).

Tutorial

Ta duy trì các tập hợp hàng rào mà chàng cao bồi thứ \(i\) sẽ tạo. Xét chàng cao bồi thứ \(i\), từ điểm \((u_{i}, v_{i})\) sẽ kẻ hàng rào theo chiều dọc xuống cắt trục \(Ox\) hoặc một hàng rào ngang \(j\) có tung độ lớn nhất và hoành độ bao phủ điểm \(u_{i}\).

Để duy trì và tìm kiếm, ta dùng segment tree với node là std::multiset. Sau khi tìm được hàng rào của chàng cao bồi thứ \(i\), ta có thể dễ dàng xem nó chứa bao nhiêu điểm bằng chặt phị phân.

Độ phức tạp: \(\mathcal{O}(m \times \log^{2} m)\).

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 300005;
const int INF = 1000000000;

struct SegmentTree {
private:
    int treeSize;
    vector<set<int>> nodes;

    void update(int node, int low, int high, int left, int right, int add) {
        if (low > right || high < left) {
            return;
        }
        if (low >= left && high <= right) {
            nodes[node].insert(add);
            return;
        }
        int mid = (low + high) >> 1;
        update(node << 1, low, mid, left, right, add);
        update(node << 1 | 1, mid + 1, high, left, right, add);
    }

    void get(int node, int low, int high, int pos, int val, int& result) {
        if (low > pos || high < pos) {
            return;
        }
        auto it = nodes[node].lower_bound(val);
        if (it != nodes[node].begin()) {
            --it;
            result = max(result, *it);
        }
        if (low == high) {
            return;
        }
        int mid = (low + high) >> 1;
        get(node << 1, low, mid, pos, val, result);
        get(node << 1 | 1, mid + 1, high, pos, val, result);
    }

public:
    void init(int treeSize) {
        this->treeSize = treeSize;
        int tmp = 1;
        while (tmp < treeSize) {
            tmp *= 2;
        }
        nodes.resize(tmp * 2);
    }

    void update(int left, int right, int add) {
        update(1, 1, treeSize, left, right, add);
    }

    int get(int pos, int val) {
        int result = 0;
        get(1, 1, treeSize, pos, val, result);
        return result;
    }
};

int n, m;
pair<int, int> a[MAX_N], b[MAX_N];
SegmentTree segmentTreeX, segmentTreeY;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("COWBOY.inp", "r", stdin);
    freopen("COWBOY.out", "w", stdout);

    cin >> n;
    int mx = 0, mn = INF;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].first >> a[i].second;
        mx = max(mx, a[i].first);
        mn = min(mn, a[i].first);
    }

    bool iswap = (mx == mn);

    if (iswap) {
        for (int i = 1; i <= n; ++i) {
            swap(a[i].first, a[i].second);
        }
    }

    sort(a + 1, a + 1 + n);
    cin >> m;
    vector<int> coordinateX = {0}, coordinateY = {0};
    for (int i = 1; i <= m; ++i) {
        cin >> b[i].first >> b[i].second;
        if (iswap) swap(b[i].first, b[i].second);
        coordinateX.push_back(b[i].first);
        coordinateY.push_back(b[i].second);
    }
    sort(coordinateX.begin(), coordinateX.end());
    sort(coordinateY.begin(), coordinateY.end());

    segmentTreeX.init(m + 1);
    segmentTreeY.init(m + 1);
    set<int> s;
    s.insert(0);
    for (int i = 1; i <= m; ++i) {
        auto [x, y] = b[i];
        if (y < a[1].second) {
            cout << 0 << "\n";
            continue;
        }
        int xx = upper_bound(coordinateX.begin(), coordinateX.end(), x) - coordinateX.begin();
        int yy = upper_bound(coordinateY.begin(), coordinateY.end(), y) - coordinateY.begin();
        int u = segmentTreeX.get(xx, y);
        int v = segmentTreeY.get(yy, x);
        int xxx = upper_bound(coordinateX.begin(), coordinateX.end(), v) - coordinateX.begin();
        int yyy = upper_bound(coordinateY.begin(), coordinateY.end(), u) - coordinateY.begin();
        segmentTreeX.update(xxx, xx, y);
        segmentTreeY.update(yyy, yy, x);
        if (u < a[1].second) {
            auto it = s.lower_bound(x);
            --it;
            int uu = upper_bound(a + 1, a + 1 + n, make_pair(x, INF)) - a - 1;
            int vv = upper_bound(a + 1, a + 1 + n, make_pair(*it, INF)) - a;
            cout << max(0, uu - vv + 1) << "\n";
            s.insert(x);
        } else {
            cout << 0 << "\n";
        }
    }

    return 0;
}

Subtask \(2\) (\(30\%\) số điểm): \(n, m \le 2 \times 10^{3}\).

Tutorial

Ta xét thuật toán gồm \(3\) bước như sau:

  • Xác định trạng thái hàng rào cuối cùng.
  • Đếm số con ngựa mỗi vùng.
  • Làm ngược các truy vấn. Mỗi lần bỏ hàng rào ra thì ta sẽ hợp nhất hai vùng với nhau (có thể dùng dsu).

Bước \(1\) và \(2\) có thể làm cùng lúc bằng thuật toán sweepline. Ngoài ra ta cũng đồng thời tìm được vùng sẽ được hợp nhất theo như truy vấn \(3\).

Thuật toán sweepline:

  • Ta xét các con ngựa và các chàng cao bồi theo thứ tự toạ độ \(y\) giảm dần. Tại mỗi bước, ta cần duy trì tập hợp các hàng rào theo chiều dọc mà chưa chạm vào hàng rào theo chiều ngang nào (nghĩa là chạm vào trục \(Ox\)).
  • Khi xét một con ngựa, ta tìm hàng rào gần nhất về bên phải. Đó sẽ là vùng chứa con trâu ở trạng thái cuối cùng.
  • Khi xét một chàng cao bồi, ta tìm vùng gần nhất sẽ được hợp nhất giống như trên: hàng rào gần nhất về bên phải. Chàng cao bồi này sẽ làm một vài hàng rào không được xét nữa. Đó là những hàng rào có toạ độ \(x\) nhỏ hơn nó nhưng xuất hiện sau (chỉ số ban đầu lớn hơn). Ta chỉ cần xoá chúng khỏi tập hợp.

Độ phức tạp: \(\mathcal{O}((n + m) \times m)\).

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 300005;

struct Point {
    int x, y, time;
    Point(int _x = 0, int _y = 0, int _time = 0) : x(_x), y(_y), time(_time) {}
    bool operator>(const Point &other) const {
        return (y == other.y ? time > other.time : y > other.y);
    }
} a[2 * MAX_N];

int numHorse, numCowboy;
vector<pair<int, int>> s;
int fa[MAX_N], num[MAX_N];
int parent[MAX_N];
int answer[MAX_N];

int find(int x) {
    return (parent[x] == 0 ? x : parent[x] = find(parent[x]));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("COWBOY.inp", "r", stdin);
    freopen("COWBOY.out", "w", stdout);
    cin >> numHorse;
    int cnt = 0;
    for (int i = 1; i <= numHorse; i++) {
        int x, y;
        cin >> x >> y;
        a[++cnt] = Point(x, y, 0);
    }
    cin >> numCowboy;
    for (int i = 1; i <= numCowboy; i++) {
        int x, y;
        cin >> x >> y;
        a[++cnt] = Point(x, y, i);
    }
    sort(a + 1, a + cnt + 1, greater<Point>());
    for (int i = 1; i <= cnt; i++) {
        if (a[i].time) {
            for (auto [u, v] : s) {
                if (u >= a[i].x) {
                    fa[a[i].time] = v;
                    break;
                }
            }
            int idx = -1;
            for (int j = 0; j < (int)s.size(); ++j) {
                if (s[j] >= make_pair(a[i].x, a[i].time)) {
                    idx = j;
                    s.insert(s.begin() + j, make_pair(a[i].x, a[i].time));
                    break;
                }
            }
            if (idx == -1) {
                idx = s.size();
                s.push_back(make_pair(a[i].x, a[i].time));
            }
            int prevIdx = idx--;
            while (idx >= 0 && s[idx].second > a[i].time) {
                --idx;
            }
            s.erase(s.begin() + idx + 1, s.begin() + prevIdx);
        } else {
            for (auto [u, v] : s) {
                if (u >= a[i].x) {
                    num[v]++;
                    break;
                }
            }
        }
    }

    for (int i = numCowboy; i >= 1; i--) {
        answer[i] = num[find(i)];
        if (fa[i]) {
            int x = find(i), y = find(fa[i]);
            parent[x] = y;
            num[y] += num[x];
        }
    }

    for (int i = 1; i <= numCowboy; i++) {
        cout << answer[i] << '\n';
    }
    return 0;
}

Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Tutorial

Nhận thấy cách thao tác xử lí trên đều có thể dùng một std::set để duy trì và thực hiện.

Độ phức tạp: \(\mathcal{O}((n + m) \times \log_{2} m)\).

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

const int MAX_N = 300000;

int n;
struct Buffalo {
    int x, y;
} b[MAX_N];

int m;
struct Settler {
    int x, y;
    int x_fence = 0;
    int y_fence = 0;
    int buffalos_start = 0;
    int buffalos_end = 0;
    int parent_end = -1;
} s[MAX_N];

struct Group {
    Group* parent = nullptr;
    int rank = 0;
    int buffalos = 0;
} group[MAX_N];


struct Vertical {
    int x, index;
};

bool operator<(const Vertical& a, const Vertical& b) {
    return a.x != b.x ? a.x < b.x : a.index < b.index;
}

struct Event {
    int y, index;
    enum Type { FENCE_POST = 1,
                BUFFALO = 2 } type;
};

bool operator<(const Event& a, const Event& b) {
    return a.y != b.y ? a.y > b.y : a.type < b.type;
}

void Sweep() {
    set<Vertical> active;
    vector<Event> events;
    events.reserve(n + m);
    for (int i = 0; i < n; ++i) {
        events.push_back(Event{b[i].y, i, Event::BUFFALO});
    }
    for (int i = 0; i < m; ++i) {
        events.push_back(Event{s[i].y, i, Event::FENCE_POST});
    }
    sort(events.begin(), events.end());
    for (const Event& e : events) {
        if (e.type == Event::FENCE_POST) {
            const auto it = active.insert(Vertical{s[e.index].x, e.index}).first;
            auto next = it;
            if (++next != active.end()) {
                s[e.index].parent_end = next->index;
            }

            auto curr = it;
            auto prev = curr;
            while (prev != active.begin()) {
                --prev;
                if (prev->index < e.index) {
                    break;
                }
                s[prev->index].y_fence = e.y;
                curr = prev;
            }
            if (prev != curr) {
                s[e.index].x_fence = prev->x;
            }
            active.erase(curr, it);
        } else {
            const auto it = active.lower_bound(Vertical{b[e.index].x, -1});
            if (it != active.end()) {
                ++s[it->index].buffalos_end;
            }
        }
    }
}

Group* Find(Group* a) {
    if (a->parent == nullptr) {
        return a;
    }
    return a->parent = Find(a->parent);
}

Group* Union(Group* a, Group* b) {
    if (a->rank < b->rank) {
        swap(a, b);
    }
    if (a->rank == b->rank) {
        ++a->rank;
    }
    b->parent = a;
    a->buffalos += b->buffalos;
    return a;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("COWBOY.inp", "r", stdin);
    freopen("COWBOY.out", "w", stdout);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> b[i].x >> b[i].y;
    }
    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> s[i].x >> s[i].y;
    }

    Sweep();
    for (int i = m - 1; i >= 0; --i) {
        Group* g = Find(&group[i]);
        g->buffalos += s[i].buffalos_end;
        s[i].buffalos_start = g->buffalos;
        if (s[i].parent_end != -1) {
            Group* p = Find(&group[s[i].parent_end]);
            Union(g, p);
        }
    }
    for (int i = 0; i < m; ++i) {
        cout << s[i].buffalos_start << '\n';
    }
    return 0;
}

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.