boj 8330 순열

https://www.acmicpc.net/problem/8330

 

수열이 a1, a2, ..., an 으로 주어졌을때 1 ~ ai 범위의 숫자를 적절하게 골라서 1 ~ N의 수가 하나씩 등장하도록 만들어야 합니다.

 

5
3 4 3 2 5

즉 이런 수열이 주어졌을 때

a1은 1 ~ 3 중에서 2

a2는 1 ~ 4 중에서 4

a3은 1 ~ 3 중에서 3

a4는 1 ~ 2 중에서 1

a5는 1 ~ 5 중에서 5

이렇게 골라서 1 ~ N까지 하나씩 등장하도록 순열을 만들 수 있습니다.

그리고 수열을 M번 수정하여 각각 수정된 수열에서도 위처럼 1 ~ N을 만들 수 있는지 구하는 문제입니다.

 

이 문제에서 저는 Segment Tree Lazy를 사용했고, 트리에는 해당 숫자를 몇 번 사용할 수 있는지 카운팅을 해줍니다.

1 ~ 5가 있다면

1은 1번, 2는 2번, 3은 3번, 4는 4번, 5는 5번 사용할 수 있습니다.

5 5 5 5 5가 입력된다면 5에서 수를 5번 고른다는 뜻입니다.

만약 4 4 4 4 4가 입력된다면 5개의 4에서 1 ~ 5를 하나씩 만들 수가 없게 되는거죠.

그렇게 i ~ N을 +1씩 업데이트를 해주고, 각각 노드에서의 최솟값으로 갱신하도록 합니다.

 

그 다음에는 최초로 주어진 수열에서 1 ~ N을 만들 수 있는지 먼저 확인합니다.

list[i]를 사용한게 되기 때문에 list[i] ~ N의 범위에 -1로 업데이트를 시켜줍니다.

트리를 최솟값으로 저장한 이유는 이 연산 과정에서 해당 값의 카운트가 음수인 경우를 빠르게 캐치하기 위해서입니다.

수열의 모든 수를 대상으로 업데이트가 끝난다면 query 함수를 이용하여 트리의 최솟값을 가져옵니다.

최솟값이 0 이상이면 순열을 만들 수 있고, 음수면 만들 수 없습니다.

 

다음 할 작업은 idx번째 수를 x로 변경하는 것입니다.

처음에는 위에서 -1로 업데이트를 한걸 되돌려야 하는지 고민했었는데 결과적으로 시간초과가 뜨더라고요!

N은 20만, M은 50만이기 때문에 시간초과가 당연한거였습니다.

20만개의 수를 50만번 업데이트 해야되니까요.. ㅎ

 

좀더 고민했을때는 트리에는 수열에 대한 카운팅이 각각 진행된 상태였고,

어차피 업데이트되는 idx번째 수에 대해서만 카운팅을 바꿔주면 된다는 결론이 나왔습니다.

그래서 수를 업데이트 하기 전에 기존 list[idx]의 범위에 대한 업데이트를 +1로 진행해주고,

새로운 값인 x의 범위에 대한 업데이트를 -1으로 진행해주면 새로운 수열에서의 카운팅 작업이 완료되는 것입니다.

마지막에는 업데이트된 트리의 최솟값을 가져와서 0 이상이면 `TAK`을, 음수면 `NIE`를 출력해주시면 되겠습니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 200001
using namespace std;
 
int list[MAX];
int tree[MAX << 2];
int lazy[MAX << 2];
int N, M;
 
void lazyUpdate(int node, int l, int r) {
    if (!lazy[node]) return;
    tree[node] += lazy[node];
    if (l != r) {
        lazy[node << 1] += lazy[node];
        lazy[(node << 1) + 1] += lazy[node];
    }
    lazy[node] = 0;
}
 
int update(int node, int l, int r, int s, int e, int diff) {
    lazyUpdate(node, l, r);
    if (l > e || s > r) return tree[node];
    if (s <= l && r <= e) {
        lazy[node] += diff;
        lazyUpdate(node, l, r);
        return tree[node];
    }
 
    int m = (l + r) >> 1;
    return tree[node] = min(update(node << 1, l, m, s, e, diff), update((node << 1) + 1, m + 1, r, s, e, diff));
}
 
int query(int node, int l, int r, int s, int e) {
    lazyUpdate(node, l, r);
    if (l > e || s > r) return 0;
    if (s <= l && r <= e) return tree[node];
 
    int m = (l + r) >> 1;
    return min(query(node << 1, l, m, s, e), query((node << 1) + 1, m + 1, r, s, e));
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        update(1, 1, N, i, N, 1);
    }
 
    for (int i = 0; i < N; i++) {
        update(1, 1, N, list[i], N, -1);
    }
}
 
void print() {
    if (query(1, 1, N, 1, N) >= 0) cout << "TAK\n";
    else cout << "NIE\n";
}
 
void func() {
    init();
    print();
 
    int idx, x;
    while (M--) {
        cin >> idx >> x;
        update(1, 1, N, list[idx - 1], N, 1);
        update(1, 1, N, x, N, -1);
        list[idx - 1] = x;
        print();
    }
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
    cin >> M;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}