BOJ 25392 - 사건의 지평선 (D3)

사용 알고리즘

Segment Tree + SCC + 위상정렬 dp

 

풀이

일단 어떻게 했는진 몰라도 i->L~R 간선을 잘 이어줬다고 치자.

무한 번 표시된다 = 사이클에서 돌고 있다는 의미이다.

따라서 사이클 내부에서 가장 큰 원소를 찾으면 그 사이클 내부에서의 정답이 된다. 단 어떤 사이클 u에서 v로 간선이 있는경우, u에서의 정답은 max(u 내부에서의 정답, v 내부에서의 정답)이다. 따라서 위상정렬 dp로 순차적으로 사이클에서의 최댓값을 결정해나가면 된다.

 

이제 i->L~R 간선을 깔끔하게 처리하는 법만 생각하면 된다. L~R은 구간이다. 구간 크기가 O(N)이므로 간선이 최대 O(N^2)개가 생긴다.

그렇다면 구간을 O(logN) 정도로 표현할 수 있다면 추가해야 하는 간선은 O(NlogN)개 일 것이다. 구간을 O(logN)으로 분할하는 자료 구조는 바로 세그먼트 트리이다. 따라서 세그먼트 트리의 구조를 변형해 다음과 같은 그래프를 모델링하면 된다.

빨간색이 도착점, 파란색이 시작점이라고 생각하자.

 

정확히 세그먼트 트리는 아니고 세그먼트 트리 형태의 그래프인데, 간선 추가를 세그먼트 트리 스타일로 한다고 생각하면 편하다.

어쨌든 이 형태가 아무 간선도 없을 때이고, 여기서 구간 간선을 추가하려면 세그먼트 트리처럼 하면 된다.

예를 들어 1->[2~4]를 추가한다고 하면, 1->2, 1->[3~4]로 쪼개서 다음과 같이 간선을 이어준다.

이렇게 하면 구간 [L,R]이 O(logN)개로 쪼개져 그만큼의 간선이 만들어지므로 O(NlogN)개의 간선이 만들어지고, 여기서 SCC를 뽑아 위상정렬을 해야하므로 시간복잡도는 O(NlogN)이다. 상수는 큰 편이다.

using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
typedef long long ll;
ll n;
int a[303030*8];
int num[303030];
vector<int> adj[303030*8], adj_s[303030*8];
ll M, MM;
struct segtree_graph{
    void init(ll node, ll s, ll e, bool flag){
        if(!flag)M = max(M,node);
        else MM = max(MM,node+M);
        if(s==e){
            if(!flag)num[s] = node;
            else adj[node+M].push_back(num[s]);
            return;
        }
        ll mid = s+e>>1;
        init(node*2,s,mid,flag); init(node*2+1,mid+1,e,flag);
        if(!flag){
            adj[node*2].push_back(node);
            adj[node*2+1].push_back(node);
        }
        else{
            adj[node+M].push_back(node*2+M);
            adj[node+M].push_back(node*2+M+1);
        }
    }
    void get(ll node, ll s, ll e, ll l, ll r, ll idx){
        if(e<l or r<s)return;
        if(l<=s and e<=r){
            adj[num[idx]].push_back(node+M);
            return;
        }
        ll mid = s+e>>1;
        get(node*2,s,mid,l,r,idx); get(node*2+1,mid+1,e,l,r,idx);
    }
} seg;
ll cnt, scnt;
int dfsn[303030*8], sccn[303030*8];
stack<int> s;
bool finished[303030*8];
ll dfs(ll x){
    dfsn[x] = ++cnt;
    s.push(x);
    ll res = cnt;
    for(auto next : adj[x]){
        if(!dfsn[next])res = min(res,dfs(next));
        else if(!finished[next])res = min(res,(ll)dfsn[next]);
    }
    if(res==dfsn[x]){
        scnt++;
        while(1){
            ll top = s.top(); s.pop();
            sccn[top] = scnt;
            finished[top] = 1;
            if(top==x)break;
        }
    }
    return res;
}
int ans[303030*8];
int ind_s[303030*8];
int main(){
    fast;
    cin>>n;
    seg.init(1,1,n,0);
    seg.init(1,1,n,1);
    for(int i = 1 ; i <= n ; i++)cin>>a[num[i]];
    for(int i = 1 ; i <= n ; i++){
        ll a,b; cin>>a>>b;
        seg.get(1,1,n,a,b,i);
    }
    for(int i = 1 ; i <= MM ; i++){
        if(!dfsn[i])dfs(i);
    }
    for(int i = 1 ; i <= MM ; i++){
        for(auto next : adj[i]){
            if(sccn[i]==sccn[next]){
                ans[sccn[i]] = max({ans[sccn[i]], a[i], a[next]});
                continue;
            }
            ind_s[sccn[i]]++;
            adj_s[sccn[next]].push_back(sccn[i]);
        }
    }
    queue<ll> q;
    for(int i = 1 ; i <= scnt ; i++)if(!ind_s[i])q.push(i);
    for(int i = 1 ; i <= scnt ; i++){
        ll cur = q.front(); q.pop();
        for(auto next : adj_s[cur]){
            ans[next] = max(ans[next],ans[cur]);
            if(--ind_s[next]==0)q.push(next);
        }
    }
    for(int i = 1 ; i <= n ; i++)cout<<ans[sccn[num[i]]]<<" ";
}

추가로 [L~R] -> [L2~R2]로 간선을 이어서 다익스트라를 하는 문제도 있다. 자주 등장하지는 않지만 이렇게 세그먼트 트리를 이용해서 구간 간선을 잇는 것도 일종의 유형으로 여겨지는 것 같다.