BOI 2018 Day2 - Alternating Current

Created2021-07-07Updated2021-07-07

題目連結

題目

有一個長度為nn個環形序列，上面有mm個線段，線段ii的左右界分別為li,ril_i, r_i，因為是環形區間，所以li>ril_i > r_i是允許的，現在請在每個線段塗上紅色或藍色，使的每個位置都至少被一個紅色線段與一個藍色線段覆蓋。

subtask

  1. 2≤n,m≤152 \leq n, m \leq 15，Score 13
  2. 2≤n,m≤1002 \leq n, m \leq 100，Score 20
  3. 2≤n,m≤10002 \leq n, m \leq 1000，Score 22
  4. 2≤n,m≤100000,∀1≤i≤m,li≤ri2 \leq n, m \leq 100000, \forall 1 \leq i \leq m, l_i \leq r_i，Score 19
  5. 2≤n,m≤1000002 \leq n, m \leq 100000，Score 26

賽中我的作法

首先，將序列中每一個位置存下該位置被哪些線段覆蓋，接下來考慮以下case:

  1. 若存在一個位置覆蓋的線段數 < 2，那顯然無解
  2. 若某位置覆蓋的線段數 = 2，代表那兩個線段必須是一紅一藍，就在那兩個線段之間建一條邊

之後做一遍dfs，即可將所有有連邊出去的線段都先塗上顏色了
順便判一下有沒有奇環，有的話顯然無解

接下來對於剩下的線段就可以greedy填，看看一個位置有哪些顏色沒被塗到，就隨便選一個覆蓋該位置且尚未被塗色的線段塗色就好

以上方法複雜度為O(nm)\mathcal{O}(nm)，滿分解的話可以運用跟TOI 2021 一模pD類似的方法
第一步可以使用一棵線段樹，存下對應區間被那些線段完全覆蓋
之後判斷線段數相當於一次query到根，沿途計算數量
再之後「判斷一個位置有哪些顏色沒被塗到」，以及「選一個覆蓋該位置且尚未被塗色的線段」一樣可以利用線段樹query一次到根，沿途好好維護該區間是否有線段被塗成紅色與藍色以及尚未被塗色的線段編號們

這樣一來均攤複雜度會是好的，O(n+mlogn)\mathcal{O}(n + mlogn)

一切都相當合理，傳上去也會AC，然而這是個假解

反例的話可以自行構造看，我覺得構造的思考過程蠻有趣的XD

反例

n=4,m=6n = 4, m = 6，線段覆蓋的位置：[1,2],[3,4],[4,1,2],[4,1],[2],[3][1, 2], [3, 4], [4, 1, 2], [4, 1], [2], [3]
首先，dfs時會先將[3,4][3, 4]塗上藍，[3][3]塗上紅
接著從位置1開始看，假設不小心將[4,1][4, 1]塗上藍，[1,2][1, 2]塗上紅
之後再看位置2，假設又不小心將[4,1,2][4, 1, 2]塗上藍，這樣就掛了，因為位置44全部都是藍色

修正

很明顯的是後面的greedy出了問題，戳了一些人的解之後發現了另一種greedy法：

首先一樣先做dfs，然後先將該塗的顏色塗好
接著先假設所有剩下的線段都是紅色，然後跑過每一條邊，若將該線段變成藍色，不會出錯(即為：區間每個位置的紅色數量皆 > 1)，那就把它改成藍色，直到結束

證明

因為想很久都構不出反例，就試著證了一下正確性

由於greedy的策略，可以確定每個位置至少會有一個紅色線段，也因此我們只要證明每個位置至少會有一個藍色線段即可

Case1: 該位置沒有線段在dfs時先被塗上顏色

  1. 對於任意三個通過相同位置的線段，必存在一個線段使得他被另外兩個線段的聯集完全包含

首先，若這三個線段其中兩個已經完全包含了，那就顯然成立，否則線段會符合l1<l2<l3<r1<r2<r3l_1 < l_2 < l_3 < r_1 < r_2 < r_3，如下圖

那這時也顯然成立，只要選第2條線段即可

  1. 在greedy塗色的過程中，任意位置的紅色線段數量最多為2

由於前面的結論，任三個線段必存在一個線段，需要其他兩個線段至少有一個被塗成藍色才可能被塗成紅色，所以不可能有三個通過相同位置的線段都被塗上紅色

由於greedy塗色的步驟中，每個位置的線段數 > 2，這代表至少會有1個藍色線段，因此證明完畢

Case2: 該位置有線段在dfs時先被塗上顏色

首先，要是線段被塗上的顏色為紅色，那就和前面的情況相同，紅色線段數的上界仍然為2，而若被塗上的顏色為藍色就顯然直接成立了

另外要說明的是一個位置在dfs時最多只會有兩個線段先被塗上顏色，原因是只有往左或往右兩種可能，因此不會有因為dfs就直接被卡住的問題

code

實作上前面判斷數量可以使用set + sweep line，而後面greedy可以使用一棵求最小值的線段樹，相較前面的假解實作輕鬆不少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define test(args...) abc("[" + string(#args) + "]", args)
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
const int mod = 1e9 + 7, N = 100000;

struct Seg {
    int l, r, m, mn, lz;
    Seg* ch[2];
    Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), mn(0), lz(0) {
        if (r - l > 1) {
            ch[0] = new Seg(l, m);
            ch[1] = new Seg(m, r);
        }
    }
    void pull() {mn = min(ch[0]->mn, ch[1]->mn);}
    void give(int v) {mn += v, lz += v;}
    void push() {ch[0]->give(lz), ch[1]->give(lz), lz = 0;}
    void add(int a, int b, int v) {
        if (a <= l && r <= b) give(v);
        else {
            push();
            if (a < m) ch[0]->add(a, b, v);
            if (m < b) ch[1]->add(a, b, v);
            pull();
        }
    }
    int query(int a, int b) {
        if (a <= l && r <= b) return mn;
        push();
        int ans = 1 << 30;
        if (a < m) ans = min(ans, ch[0]->query(a, b));
        if (m < b) ans = min(ans, ch[1]->query(a, b));
        return ans;
    }
};

int color[N];
bool odd_cycle;
vector <int> adj[N];

void dfs(int v) {
    for (int u : adj[v]) {
        if (!color[u]) {
            color[u] = 3 ^ color[v];
            dfs(u);
        } else if (color[u] == color[v]) {
            odd_cycle = true;
        }
    }
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <int> l(m), r(m);
    vector <pii> event;
    for (int i = 0; i < m; ++i) {
        cin >> l[i] >> r[i], --l[i];
        if (l[i] != r[i]) event.eb(l[i], i), event.eb(r[i], i);
        if (l[i] >= r[i]) event.eb(0, i);
    }
    sort(all(event));
    set <int> on;
    for (int i = 0, j = 0; i < n; ++i) {
        for (; j < event.size() && event[j].X == i; ++j) {
            if (on.count(event[j].Y)) on.erase(event[j].Y);
            else on.insert(event[j].Y);
        }
        if (on.size() < 2) return cout << "impossible\n", 0;
        else if (on.size() == 2) {
            int u = *on.begin(), v = *on.rbegin();
            adj[u].pb(v), adj[v].pb(u);
        }
    }
    for (int i = 0; i < m; ++i) if (!color[i] && !adj[i].empty()) {
        color[i] = 1;
        dfs(i);
    }
    if (odd_cycle) return cout << "impossible\n", 0;
    Seg root(0, n);
    auto add = [&](int i, int v) {
        if (l[i] >= r[i]) root.add(l[i], n, v), root.add(0, r[i], v);
        else root.add(l[i], r[i], v);
    };
    auto qry = [&](int i) {
        if (l[i] >= r[i]) return min(root.query(l[i], n), root.query(0, r[i]));
        return root.query(l[i], r[i]);
    };
    for (int i = 0; i < m; ++i) if (color[i] != 1) add(i, 1);
    for (int i = 0; i < m; ++i) if (!color[i]) {
        if (qry(i) == 1) color[i] = 2;
        else color[i] = 1, add(i, -1);
    }
    for (int i = 0; i < m; ++i) cout << color[i] - 1;
    cout << endl;
}

後記

原本其實是想要證明自己賽中的解，結果在證明的時候越想越怪就構了個反例
後來翻到的解原本以為是錯的，想構反例但卻構不出來，就自己想了一個證明出來
希望證明沒有假解> <