BOJ 12016 - 라운드 로빈 스케줄러 링크
(2023.09.05 기준 P3)

문제

작업에 필요한 시간과 함께 N개의 작업이 주어진다. 각 작업을 1초씩 차례대로 실행시키고, 완료된 작업은 앞으로 실행시키지 않는다. 이때, 각 작업이 언제 완료되는지 출력

알고리즘

구간합 세그먼트 트리를 곁들인 오프라인 쿼리

풀이

작업들을 작업에 필요한 시간과 인덱스를 기준으로 정렬해보자.
그리고 아직 끝나지 않은(활성화된) 작업은 1, 끝난(비활성화된) 작업은 0으로 나타나는 구간합 세그먼트 트리를 만들자.

만약, 위와 같이 작업에 필요한 시간이 같은 두 쿼리가 있다면?
[직전 인덱스 + 1, 현재 인덱스] 구간에 있는 활성화된 작업 수 + 직전 작업의 걸리는 시간 = 현재 작업의 걸리는 시간이 된다.

만약, 위와 같은 두 쿼리가 주어진다면?
[직전 인덱스 + 1, 끝] 구간에 있는 활성화된 작업 수 + (시간 차이 - 1) × 전체 활성화된 작업수 + [처음, 현재 인덱스] 구간에 있는 활성화된 작업 수 + 직전 작업의 걸리는 시간 = 현재 작업의 걸리는 시간이 된다.

위 두 경우에 맞게 정렬된 쿼리를 차례대로 처리하면서, 쿼리 하나를 처리할 때마다 결과를 저장함과 동시에 그 쿼리의 작업을 비활성화하면 된다.

코드

• C++

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

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 100000, MAXH = 1 << (int)(ceil(log2(MAXN) + 1));

int tree[MAXH];

void init(int nd, int st, int en){
    if (st == en){
        tree[nd] = 1; // 초기엔 모든 작업이 활성화되어 있다.
        return;
    }
    int mid = (st + en) >> 1;
    init(nd << 1, st, mid);
    init(nd << 1 | 1, mid + 1, en);
    tree[nd] = tree[nd << 1] + tree[nd << 1 | 1];
}

void update(int nd, int st, int en, int idx, int val){
    if (st == en){
        tree[nd] += val;
        return;
    }
    int mid = (st + en) >> 1;
    if (idx <= mid) update(nd << 1, st, mid, idx, val);
    else update(nd << 1 | 1, mid + 1, en, idx, val);
    tree[nd] = tree[nd << 1] + tree[nd << 1 | 1];
}

int query(int nd, int st, int en, int l, int r){
    if (r < st || en < l) return 0;
    if (l <= st && en <= r) return tree[nd];
    int mid = (st + en) >> 1;
    return query(nd << 1, st, mid, l, r) + query(nd << 1 | 1, mid + 1, en, l, r);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    int T[N]; for (int i = 0; i < N; i++) cin >> T[i];

    // 세그먼트 트리 생성
    init(1, 0, N - 1);

    // 먼저 끝나는 작업 순으로 쿼리를 정렬
    vector<pii> queries;
    for (int i = 0; i < N; i++) queries.push_back({T[i], i});
    sort(queries.begin(), queries.end());
    ll result[N]; // 쿼리 결과를 담을 배열

    ll prev = 0; // 직전 쿼리 결과
    int turn = 1, idx = -1; // 직전 턴 수, 직전 쿼리 인덱스
    for (auto [t, i]: queries){

        // 직전 쿼리와 턴 수가 같다면 [idx, i] 구간에 있는 활성화되어 있는 작업 수를 구하자.
        if (turn == t) result[i] = prev + query(1, 0, N - 1, idx + 1, i);

        // [idx, N - 1], [0, N - 1], [0, i] 구간에 있는 활성화되어 있는 작업 수를 구하자.
        else result[i] = prev + query(1, 0, N - 1, idx + 1, N - 1) + (ll)(t - turn - 1) * tree[1] + query(1, 0, N - 1, 0, i);

        // 현재 쿼리의 작업은 이제 끝났으므로 비활성화시키자.
        update(1, 0, N - 1, i, -1);
        prev = result[i];
        turn = t;
        idx = i;
    }

    for (int i = 0; i < N; i++) cout << result[i] << '\n';
}

• Python

import sys; input = sys.stdin.readline
from math import ceil, log2

def init(nd, st, en):
    if st == en:
        tree[nd] = 1 # 초기엔 모든 작업이 활성화되어 있다.
        return
    mid = (st + en) >> 1
    init(nd << 1, st, mid)
    init(nd << 1 | 1, mid + 1, en)
    tree[nd] = tree[nd << 1] + tree[nd << 1 | 1]

def update(nd, st, en, idx, val):
    if st == en:
        tree[nd] += val
        return
    mid = (st + en) >> 1
    if idx <= mid:
        update(nd << 1, st, mid, idx, val)
    else:
        update(nd << 1 | 1, mid + 1, en, idx, val)
    tree[nd] = tree[nd << 1] + tree[nd << 1 | 1]

def query(nd, st, en, l, r):
    if r < st or en < l:
        return 0
    if l <= st and en <= r:
        return tree[nd]
    mid = (st + en) >> 1
    return query(nd << 1, st, mid, l, r) + query(nd << 1 | 1, mid + 1, en, l, r)

N = int(input())
T = list(map(int, input().split()))

# 세그먼트 트리 생성
tree = [0] * (1 << ceil(log2(N) + 1))
init(1, 0, N - 1)

# 먼저 끝나는 작업 순으로 쿼리를 정렬
queries = sorted((T[i], i) for i in range(N))
result = [0] * N # 쿼리 결과를 담을 배열

prev = 0; turn = 1; idx = -1 # 직전 쿼리 결과, 직전 턴 수, 직전 쿼리 인덱스
for t, i in queries:

    # 직전 쿼리와 턴 수가 같다면 [idx, i] 구간에 있는 활성화되어 있는 작업 수를 구하자.
    if turn == t:
        result[i] = prev + query(1, 0, N - 1, idx + 1, i)

    # [idx, N - 1], [0, N - 1], [0, i] 구간에 있는 활성화되어 있는 작업 수를 구하자.
    else:
        result[i] = prev + query(1, 0, N - 1, idx + 1, N - 1) + (t - turn - 1) * tree[1] + query(1, 0, N - 1, 0, i)

    # 현재 쿼리의 작업은 이제 끝났으므로 비활성화시키자.
    update(1, 0, N - 1, i, -1)
    prev = result[i]
    turn = t
    idx = i

print(*result, sep = '\n')