백준 10755번 컴퓨터실

문제 요약

COI 2015 3번 문제이다. 현재 기준으로 솔브드 티어는 다이아 4다.

1부터 M까지의 숫자가 부여된 자리가 순서대로 일직선 상에 놓여 있고, 이미 차 있는 자리가 N개 주어진다. 그리고 M-N개의 자리는 다음과 같은 순서로 채워진다.

• 비어있는 연속 구간들 중에서 가장 길이가 긴 구간을 고른다. 그리고 그 구간의 중앙에 앉는다. 구간의 길이 L이 짝수일 경우에는 L/2번째 자리에 앉는다.
• 길이가 가장 긴 구간들이 여러개 있을 경우에는 앞쪽의 구간을 고른다.

이러한 방식으로 자리를 채워나갈 때, Q개의 숫자 $b_i$가 주어진다. 문제에서 원하는 출력은 $b_i$번째에 채워진 자리의 위치이다.

제한은 $ 1 \leq N \leq 10^5 $, $ N \leq M $, $ 1 \leq Q \leq 10^5 $, $ 1 \leq M \leq 10^{14} $이다.

풀이

문제를 보자마자 생각할만한 풀이로는 주어진 $N$개의 수들로 나눠지는 구간들을 전부 우선순위 큐에 넣고 실제로 시뮬레이션하는 풀이이다. 다만, 이 경우에 $b_i$가 최대 $M$까지 커질 수 있어서 총 시간복잡도는 $O(MlogM)$으로 아쉽게도 시간초과가 난다.

문제를 풀기 위해서는 다음과 같은 관찰이 큰 도움을 준다.

길이 $L$의 구간에서 나올 수 있는 구간의 길이의 종류는 많아 봤자 $2log_2L$이다.

하나의 구간이 선택되서 쪼개질 때는 $L$이 홀수일 경우에는 $\frac{L-1}{2}$인 구간 두개로, 짝수일 경우에는 왼쪽은 $\frac{L-1}{2}$, 오른쪽은 $\frac{L}{2}$인 구간으로 쪼개진다. 여기서 나눗셈은 정수나눗셈으로 floor division이다.

한번씩 더 쪼자. $L$이 짝수일 때 $\frac{L-1}{2}$은 홀수이므로 $\frac{\frac{L-1}{2} - 1}{2}$인 구간 두 개로 쪼개지고, $\frac{L}{2}$은 $\frac{\frac{L}{2} - 1}{2}$과 $\frac{L}{4}$로 쪼개진다. 여기서 $ \frac{L}{4} = \frac{\frac{L-1}{2} - 1}{2} $이다.

$L$이 홀수일 때 $\frac{L-1}{2}$은 짝수이므로 왼쪽은 $\frac{\frac{L-1}{2} - 1}{2}$. 오른쪽은 $\frac{\frac{L-1}{2}}{2}$인 구간으로 쪼개진다.

이 수들을 잘 보면 처음 $L$을 나눌 때도 구간의 길이의 종류는 최대 2개고, 그 다음에 나눌 때도 최대 2개인 것을 알 수 있다. 그리고 이는 쭉 반복될 것이다.

이로부터 길이가 $L$인 구간에서 나올 수 있는 구간의 길이의 종류의 수가 많아 봤자 $2log_2L$인 것을 확인할 수 있다.

그럼 이 사실을 어떻게 활용할까. 처음에 $N$개의 숫자가 주어진다. 이를 통해 만들어지는 구간은 $N$개 혹은 $N+1$개다. 편의상 그냥 $N$개라고 하겠다. 이러한 구간들을 main segment라고 하고, 0부터 N-1까지로 순서를 부여하자.

발견한 사실을 이용하면 이 $N$개의 main segment 각각에 속해 있는 구간들의 길이, 그 길이를 가지는 구간의 개수를 구해낼 수 있다. 이를 통해서 하나의 구간에서 다음과 같은 순서쌍들을 뽑아내자.

$$
(len, cnt, main_segment_idx)
$$

이러한 순서쌍이 최대 $O(logL)$정도 있으며 모든 main segment에 대해서 구하면 $O(NlogM)$정도 있을 것이다. 이 순서쌍들을 문제에서 제시한대로 정렬하자. 길이가 큰 놈이 앞에 오고, 길이가 같다면 main segment가 앞에 있는 쪽이 더 앞으로 오게 정렬하면 된다.

여기까지의 시간복잡도를 계산하자. main segment가 $N$개 존재하며, main segment는 최대 길이가 $M$까지 갈 수 있다. 그러면 길이가 $M$인 구간에 대해서 저 순서쌍들을 다 구하는 데에는 어느정도 시간이 걸릴까? 일단 $M$을 반으로 쪼개면서 진행하기 때문에 $O(logM)$정도가 들고, 나는 각 길이를 가지는 구간들의 갯수를 기록 하는데 std::map을 사용했기 때문에 이것도 고려해야한다.

이를 고려하면 이 작업의 시간복잡도는 $O(NlogMlog(logM))$이 되겠다.

정렬의 시간복잡도를 까먹었다. 순서쌍이 $O(NlogM)$정도 있으므로, 정렬은 $O(NlogMlog(NlogM))$이다. 로그 안의 항을 분리하면 위 시간복잡도와 동일하다. 그리고 정렬된 순서쌍 벡터를 $seg$라고 하자.

이제 정렬해놓은 이걸 대체 어따 써먹어야 할까?

일단 이걸 사용해서, $b_i$번째로 자리를 채울 때 고르는 구간의 길이와 그 구간이 어느 main segment에 위치하는 지는 계산이 가능하다.이를 위해서 $seg[i].cnt$의 누적합 배열을 일단 $pre[i]$라고 하자.

정렬된 순서쌍들은 자리를 채울 때 골라지는 순서대로 정렬된 것이므로 $b_i$.번째로 자리를 채울 때 고르는 구간은 $pre[x-1] \lt b_i \leq pre[x]$에 해당하는 $seg[x]$가 될 것이다. $b_i$가 정렬된 상태로 주어지므로 $x$를 계산하는 데는 $seg$를 스위핑하면 쉽게 가능하다.

그럼 배정될 구간의 길이도 알고 그 구간이 어느 main segment에 속하는지도 알았다. 정확한 위치는?

일단 $b_i$를 알기 때문에 그 main segment에서 길이가 $len$인 구간들 중에 몇 번째 구간인지도 쉽게 구할 수 있다. 그걸 $K$라고 하자.

다시 또 구간을 나눠 보자. 구간을 쪼갰을 때, 왼쪽 구간에 길이가 $len$인 구간이 $K$개 이상 있다면, 우리가 찾고자 하는 구간은 당연히 왼쪽 구간에 속해있을 것이다. 만약에 $K$개보다 적게 있다면 오른쪽 구간에 존재하는 것이다. 이 사실을 이용해서 위치 또한 구하는 것이 가능하다.

이진트리나 세그먼트 트리에서 $kth \; element$를 구하는 것을 구하는 과정과 유사하다.

이제 이 작업을 하려면 또 필요한 게 어떤 구간의 길이가 $len$인 구간이 몇 개 있는지를 계산하는 것인데, 하나 기억해야 할 것이 어떤 구간에 길이가 $len$인 구간이 몇 개 있는 지는 오직 그 구간의 길이에만 의존한다. 왜냐면 구간을 쪼개는 작업이 오직 길이에만 의존하기 때문이다.

이 사실을 이용하여 길이가 $len$인 구간의 갯수를 구하는 것은 위에서 했던 하나의 main segment 안에서 모든 구간의 길이의 종류를 구하는 것과 비슷하게 구하면 된다.

이제 시간복잡도를 계산하자. 일단 $seg$를 스위핑할 것이기 때문에 $O(NlogM)$, 쿼리 하나당 main segment를 하나 처리한다. main segment에서 구간의 갯수를 구하는 전처리에 다시 std::map을 사용했기 때문에 전처리에 $O(logMlog(logM))$, $K$번째 구간의 위치를 구하는 것 또한 같은 시간복잡도를 가진다.

따라서 총 시간 복잡도는 $O(NlogM + QlogMlog(logM))$이 된다. 문제를 푸는 데에 총 걸리는 시간은 $O((N+Q)logMlog(logM))$이 된다.

아래는 구현한 코드다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    ll len, cnt, idx;
    bool operator< (const Node &rhs) {
        if(len == rhs.len) return idx < rhs.idx;
        return len > rhs.len;
    }
};

ll N, M, Q;
ll A[100005];
ll B[100005];
ll ans[100005];
map<ll,ll> mp;
vector<pair<ll,ll>> ret;

void calc_seg(ll len) {
    ret.clear();
    mp.clear();
    mp[len] = 1;
    while(!mp.empty()) {
        assert(mp.size() <= 100);
        auto it = prev(mp.end());
        ll l = it->first;
        ll cnt = it->second;
        if(l == 0) break;
        ret.push_back({l,cnt});
        if(l>1) {
            if(l%2) mp[l/2] += cnt*2;
            else {
                mp[l/2] += cnt;
                if(l/2 != 1) mp[l/2-1] += cnt;
            }
        }
        mp.erase(it);
    }
    return ;
}

ll calc_cache(ll len, ll target) {
    if(len < target) return 0;
    if(mp.find(len) != mp.end()) return mp[len];
    return mp[len] = calc_cache(len/2, target) + calc_cache((len-1)/2, target);
}

ll calc_pos(int idx, ll tar_len, ll K) {
    ll len = A[idx+1] - A[idx] - 1;
    ll pos = A[idx];
    mp.clear(); mp[tar_len] = 1;
    calc_cache(len, tar_len);
    while(len != tar_len) {
        ll tmp_len = (len-1)/2;
        ll cnt = mp[tmp_len];
        if(cnt >= K) len = (len-1) / 2;
        else {
            pos += tmp_len + 1;
            len >>= 1;
            K -= cnt;
        }
    }
    return pos + (len+1)/2;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> M >> N >> Q;
    for(int i=1;i<=N;++i) cin >> A[i];
    A[0] = 0; A[N+1] = M+1;
    for(int i=1;i<=Q;++i) cin >> B[i];
    vector<Node> segment;
    for(int i=0;i<=N;++i) {
        ll len = A[i+1] - A[i] - 1;
        if(len>0) {
            calc_seg(len);
            for(const auto &p:ret) segment.push_back({p.first, p.second, i});
        }
    }   // O(NlogM)
    sort(segment.begin(), segment.end()); // O(NlogM * (logN + log(logM))
    int q = 1;
    while(q <= Q && B[q] <= N) {
        ans[q] = A[B[q]];
        ++q;
    }
    ll pos = N;
    for(const auto &seg:segment) {  // O(NlogM)
        while(q<=Q && B[q] <= pos+seg.cnt) {
            ans[q] = calc_pos(seg.idx, seg.len, B[q]-pos);  // O(log^2M)
            ++q;
        }
        pos += seg.cnt;
    }
    for(int q=1;q<=Q;++q) cout << ans[q] << '\n';
    return 0;
}