백준15864 Alternating Current

작성일 | In

문제 링크

  • http://icpc.me/15864

문제 출처

  • 2018 Baltic OI Day2 1번

사용 알고리즘

  • 세그먼트 트리 + 레이지
  • 슬라이딩 윈도우

시간복잡도

  • $O(M \log M + M \log N)$

풀이

어떤 선분 $l_1$이 $l_2$에 완전히 포함된다면, $l_1$은 $l_2$와 다른 색을 배정해주면 되기 때문에 $l_1$을 없애고 생각해도 됩니다. KOI 2014 버스노선처럼 Sliding Window를 이용해 다른 선분에 완전히 포함되는 선분을 제거하고, 어떤 선분에 포함되는지만 기록합시다. (calc_elimination 함수 참고)

각 구간은 최소 한 개 이상의 선분으로 덮여있기 때문에, 어떠한 선분에도 포함되지 않는 선분들만 남겨놓은 다음 정렬하면 아래 그림처럼 나오게 됩니다.

만약 정답이 존재한다면 아래 그림처럼 색을 교차해서 놓았을 때 항상 정답이 나온다는 것을 알 수 있습니다.

어떠한 선분에도 포함되지 않은 선분의 개수를 K라고 합시다.
K가 짝수라면 위 그림처럼 색을 교차하게 놓아서 확인하면 끝날텐데, 홀수라면 약간 까다롭습니다.
K = 5라면 아래 5가지 경우를 모두 확인해야 합니다.

1
2
3
4
5
01010 (1번 선분부터 시작)
11010 (2번 선분부터 시작)
10010 (3번 선분부터 시작)
10110 (4번 선분부터 시작)
10100 (5번 선분부터 시작)

K가지 경우를 Naive하게 확인해주면 서브태스크 1, 2, 3을 해결해 55점을 받을 수 있습니다.

위에서 작성한 5가지 경우를 잘 보면, 어떤 i번째 비트열과 i-1번째 비트열은 비트 1개 밖에 차이가 나지 않는다는 것을 알 수 있습니다. K가지 경우를 모두 확인할 때 각 선분의 색깔을 1번만 바꿔도 된다는 것을 알 수 있습니다.
Segment Tree + Lazy Propagation을 사용해 구간의 최솟값을 관리하면 선분이 잘 덮여있는지 빠르게 확인해줄 수 있습니다.

선분을 정렬하고 필요 없는 선분을 제거하는데 $O(M \log M)$만큼 걸리고, 정답이 존재하는지 확인하는데 $O(M \log N)$이 걸리므로 문제를 해결할 수 있습니다.

전체 코드

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int par[101010];
vector<int> g[101010];
int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
void merge(int pa, int ch){ pa = find(pa); ch = find(ch); if(pa != ch) par[ch] = pa; }

struct Seg{
    int tree[1 << 17], tmp[1 << 17], n;
    void init(int _n){ n = _n; memset(tree, 0, sizeof tree); memset(tmp, 0, sizeof tree); }
    void push(int node, int s, int e){
        if(!tmp[node]) return;
        tree[node] += tmp[node];
        if(s != e){
            tmp[node << 1] += tmp[node];
            tmp[node << 1 | 1] += tmp[node];
        }
        tmp[node] = 0;
    }
    void update(int node, int s, int e, int l, int r, int v){
        push(node, s, e);
        if(r < s || e < l) return;
        if(l <= s && e <= r){
            tmp[node] += v; push(node, s, e);
            return;
        }
        int m = s + e >> 1;
        update(node << 1, s, m, l, r, v);
        update(node << 1 | 1, m+1, e, l, r, v);
        tree[node] = min(tree[node << 1], tree[node << 1 | 1]);
    }
    int query(int node, int s, int e, int l, int r){
        push(node, s, e);
        if(r < s || e < l) return 1e9;
        if(l <= s && e <= r) return tree[node];
        int m = s + e >> 1;
        int t1 = query(node << 1, s, m, l, r);
        int t2 = query(node << 1 | 1, m+1, e, l, r);
        return min(t1, t2);
    }
    void update(int s, int e, int x){
        if(e >= n) e -= n;
        if(s <= e) update(1, 0, n-1, s, e, x);
        else update(1, 0, n-1, 0, e, x), update(1, 0, n-1, s, n-1, x);
    }
    int query(){ return query(1, 0, n-1, 0, n-1); }
} seg[2];

struct Info{
    int s, e, x, eli, color;
    Info() : Info(0, 0, 0) {}
    Info(int s, int e, int x) : s(s), e(e), x(x), eli(-1), color(-1) {}
    bool operator < (const Info &t) const { return make_pair(s, -e) < make_pair(t.s, -t.e); }
};

int n, m, ed, ed_idx;
Info a[101010];
vector<Info> v;

int tmp[101010];

void calc_elimination(){
    deque<Info> dq;
    sort(a+1, a+m+1);
    for(int i=1; i<=m; i++){
        if(dq.empty() || dq.back().e < a[i].e) dq.push_back(a[i]);
        else tmp[a[i].x] = dq.back().x;
    }
    while(dq.size() && dq.front().e <= ed) tmp[dq[0].x] = ed_idx, dq.pop_front();
    for(auto i : dq) v.push_back(i);
    for(int i=1; i<=m; i++) if(tmp[a[i].x]) a[i].eli = tmp[a[i].x];

    iota(par, par+101010, 0);
    for(int i=1; i<=m; i++) if(a[i].eli != -1) merge(a[i].eli, a[i].x);
    for(int i=1; i<=m; i++){
        if(a[i].eli != -1) a[i].eli = find(a[i].x), g[a[i].eli].push_back(a[i].x);
        else g[a[i].x].push_back(a[i].x);
    }
}

inline bool eval(){ return seg[0].query() > 0 && seg[1].query() > 0; }

void even(){
    seg[0].init(n); seg[1].init(n);

    for(int i=0; i<v.size(); i++) a[v[i].x].color = i % 2;
    for(int i=1; i<=m; i++) if(a[i].color == -1) a[i].color = !a[a[i].eli].color;

    for(int i=1; i<=m; i++){
        seg[a[i].color].update(a[i].s, a[i].e, 1);
    }
    if(eval()){
        for(int i=1; i<=m; i++) cout << a[i].color;
    }
    else cout << "impossible";
}

void odd(){
    seg[0].init(n); seg[1].init(n);
    for(int i=0; i<v.size(); i++) a[v[i].x].color = i % 2;
    for(int i=1; i<=m; i++) if(a[i].color == -1) a[i].color = !a[a[i].eli].color;
    for(int i=1; i<=m; i++){
        seg[a[i].color].update(a[i].s, a[i].e, 1);
    }
    if(eval()){ for(int j=1; j<=m; j++) cout << a[j].color; return; }

    for(int i=0; i<v.size(); i++){
        for(auto j : g[v[i].x]){
            seg[a[j].color].update(a[j].s, a[j].e, -1);
            a[j].color ^= 1;
            seg[a[j].color].update(a[j].s, a[j].e, 1);
        }
        if(eval()){ for(int j=1; j<=m; j++) cout << a[j].color; return; }
    }
    cout << "impossible";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int s, e; cin >> s >> e; s--; e--;
        if(s > e){
            if(ed < e) ed = e, ed_idx = i;
            e += n;
        }
        a[i] = {s, e, i};
    }
    calc_elimination();
    sort(a+1, a+m+1, [](Info a, Info b){ return a.x < b.x; });
    if(v.size() % 2 == 0) even();
    else odd();
}