백준19336 Mines

작성일 | In

문제 링크

  • http://icpc.me/19336

사용 알고리즘

  • Segment Tree
  • SCC

풀이

SCC를 만들고, indegree가 0인 SCC마다 가중치가 가장 작은 것을 구해서 더해주면 됩니다. 근데 간선이 $O(N^2)$개인 것이 문제입니다.
세그먼트 트리를 이용해 그래프의 간선을 줄이는 테크닉을 이용하면 $O(N \log N)$개의 간선만으로 그래프를 만들 수 있고, 문제를 풀 수 있습니다.

indegree가 0인 SCC에서 가중치 최솟값을 구하는 것은 std::multiset을 써도 되고, 힙 2개를 이용해도 됩니다.

전체 코드

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
#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;
typedef pair<int, int> p;
const int SZ = 1 << 19;
const int INF = 1e9+7;

template<typename T, T inf>
struct pq_set{
    priority_queue<T, vector<T>, greater<T>> in, out; // min
    pq_set(){ in.push(inf); }
    void insert(T v){ in.push(v); }
    void erase(T v){ out.push(v); }
    T top(){
        while(out.size() && in.top() == out.top()) in.pop(), out.pop();
        return in.top();
    }
    bool empty(){
        while(out.size() && in.top() == out.top()) in.pop(), out.pop();
        return in.top() == inf;
    }
};

int n, q, ed; ll ans; p b[SZ];
struct Info{ int p, r, c; } a[SZ];
pq_set<int, INF> st[SZ];

namespace SCC{
    vector<int> g[SZ], r[SZ], gph[SZ], dfn;
    void addEdge(int s, int e){ g[s].push_back(e); r[e].push_back(s); }
    int chk[SZ], scc[SZ], del[SZ];
    void dfs1(int v){ chk[v] = 1; for(auto i : g[v]) if(!chk[i]) dfs1(i); dfn.push_back(v); }
    void dfs2(int v, int color){ chk[v] = 0; scc[v] = color; for(auto i : r[v]) if(chk[i]) dfs2(i, color); }
    void dfs3(int v){ del[v] = 1; for(auto i : gph[v]) if(!del[i]) dfs3(i); }
    void dfs4(int v){ chk[v] = 1; for(auto i : gph[v]) if(!del[i]) dfs3(i); }
    void getSCC(){
        for(int i=1; i<=ed; i++) if(!chk[i]) dfs1(i);
        reverse(all(dfn));
        for(auto i : dfn) if(chk[i]) dfs2(i, i);
        for(int i=1; i<=ed; i++) for(auto j : g[i]) {
            if(scc[i] != scc[j]) gph[scc[i]].push_back(scc[j]);
        }
    }
}
using namespace SCC;

namespace Seg{
    int lc[SZ], rc[SZ];
    int init(int s = 1, int e = n){
        if(s == e) return b[s].y;
        int x = ++ed;
        int m = s + e >> 1;
        lc[x] = init(s, m); rc[x] = init(m+1, e);
        addEdge(x, lc[x]); addEdge(x, rc[x]);
        return x;
    }
    void insert(int node, int s, int e, int l, int r, int v){
        if(r < s || e < l) return;
        if(l <= s && e <= r){ addEdge(v, node); return; }
        int m = s + e >> 1;
        insert(lc[node], s, m, l, r, v);
        insert(rc[node], m+1, e, l, r, v);
    }
}
using namespace Seg;

int get_left(int x){
    int l=1, r=n, t;
    while(l <= r){
        int m = l + r >> 1;
        if(x <= b[m].x) t = m, r = m - 1;
        else l = m + 1;
    }
    return t;
}
int get_right(int x){
    int l=1, r=n, t;
    while(l <= r){
        int m = l + r >> 1;
        if(b[m].x <= x) t = m, l = m + 1;
        else r = m - 1;
    }
    return t;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q; ed = n;
    for(int i=1; i<=n; i++) cin >> a[i].p >> a[i].r >> a[i].c;
    for(int i=1; i<=n; i++) b[i] = {a[i].p, i}; sort(b+1, b+n+1);
    int root = init();
    for(int i=1; i<=n; i++){
        int l = get_left(a[i].p - a[i].r);
        int r = get_right(a[i].p + a[i].r);
        insert(root, 1, n, l, r, i);
    }
    getSCC();
    for(int i=1; i<=n; i++) if(!chk[scc[i]]) dfs4(scc[i]);
    for(int i=1; i<=n; i++) if(!del[scc[i]]) st[scc[i]].insert(a[i].c);
    for(int i=1; i<=ed; i++) if(i == scc[i] && !del[i] && !st[i].empty()) ans += st[i].top();
    while(q--){
        int s, e, id; cin >> s >> e; id = scc[s];
        if(del[id]){ cout << ans << "\n"; continue; }
        ans -= st[id].top();
        st[id].erase(a[s].c);
        a[s].c = e;
        st[id].insert(a[s].c);
        ans += st[id].top();
        cout << ans << "\n";
    }
}