TIOJ 1430：[APIO '12] 衛兵問題

TIOJ 1430：[APIO '12] 衛兵問題

題目大意：有 $n$ 的點，其中 $k$ 個點藏有忍者，有 $m$ 個衛兵，每個衛兵守衛區間 $[l, r]$，若 $[l, r]$ 裡有忍者，那 $c=1$，否則 $c=0$，請你輸出一定有忍者的點。

解法：首先可以先把必為 $0$ 的點去掉，然後觀察到若一個大區間覆蓋了一個小區間，那其實可以不考慮大區間，因為小區間必有 $1$，大區間也一定會有 $1$，我們就可以得到左界遞增，右界遞增的線段，如果不必為 $0$ 的點恰好有 $k$ 個，那這時可以直接輸出答案。如果我們想算一個點是不是一定會被用到，那可以計算它沒被用到的話可不可行，可以採用一個貪心策略，維護 $lp_i, rp_i$，$lp_i$ 代表前 $i$ 個線段最少要有幾個點才能符合條件，$rp_i$ 代表第 $i\sim m$ 個線段最少要有幾個點才能符合條件。每次看一個線段，若 $l=r$，那代表一定會用到那一點，否則一個線段只有當 $lp_i>lp_{i-1}$ 時的 $r$ 可以當候選人，若要計算沒有 $r$ 時合不合法，可以令用到的是 $r$ 左邊那一點，二分搜出在 $L_{r-1}$ 前且最右邊的線段編號 $pl$，與在 $L_{r-1}$ 後且最左邊的線段編號 $pr$，若 $lp_{pl}+1+rp_{pr}>k$，那代表此點一定要被選到。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;

int n, m, k, siz;
pair<int, int> p[SIZE];
int d[SIZE], L[SIZE], R[SIZE], lp[SIZE], rp[SIZE];

void solve() {
    cin >> n >> k >> m;
    while (m--) {
        int l, r, c;
        cin >> l >> r >> c;
        if (c == 0) {
            d[l]++;
            d[r + 1]--;
        } else {
            p[++siz] = {l, r};
        }
    }
    m = siz;
    R[n + 1] = n + 1;
    int cnt = 0;
    FOR (i, 1, n) {
        d[i] += d[i - 1];
        if (d[i]) L[i] = L[i - 1];
        else {
            cnt++;
            L[i] = R[i] = i;
        }
    }
    for (int i = n; i >= 1; i--) if (d[i]) R[i] = R[i + 1];
    if (cnt == k) {
        FOR (i, 1, n) if (d[i] == 0) cout << i << '\n';
        return;
    }
    FOR (i, 1, m) p[i] = {R[p[i].F], L[p[i].S]};
    sort (p + 1, p + m + 1, [] (auto p1, auto p2) {
        return p1.S != p2.S ? p1.S < p2.S : p1.F > p2.F;
    });
    siz = 1;
    FOR (i, 2, m) if (p[i].F > p[siz].F) p[++siz] = p[i];
    m = siz, cnt = 0;
    for (int i = 1, mx = 0; i <= m; i++) {
        lp[i] = lp[i - 1];
        if (p[i].F > mx) {
            lp[i]++;
            mx = p[i].S;
        }
    }
    for (int i = m, mn = n + 1; i >= 1; i--) {
        rp[i] = rp[i + 1];
        if (p[i].S < mn) {
            rp[i]++;
            mn = p[i].F;
        }
    }
    FOR (i, 1, m) if (lp[i] > lp[i - 1]) {
        auto [l, r] = p[i];
        if (l == r) {
            cnt++;
            cout << r << '\n';
            continue;
        }
        r = L[r - 1];
        int pl = lower_bound (p + 1, p + i, r, [] (pair<int, int> x, int r) {
            return x.S < r;
        }) - p - 1;
        int pr = lower_bound (p + i + 1, p + m + 1, pair<int, int> (r, n + 1)) - p;
        if (lp[pl] + rp[pr] + 1 > k) {
            cnt++;
            cout << p[i].S << '\n';
        }
    }
    if (cnt == 0) cout << "-1\n";
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！