백준 3408 - Non-boring sequences

 

 

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

길이 $N(\leq 200000)$의 수열이 주어졌을 때, $N$의 모든 substring이 유일한 원소를 가지면 non-boring, 아니면 boring을 출력하는 문제다.

 

처음에 시도한 접근법은 아래와 같다.

1. 수열 전체에 유일한 원소가 없다면 그 수열은 boring이다.

2. 그렇지 않다면, 해당 원소를 포함한 모든 구간은 유일한 원소를 가진다.

3. 따라서 해당 원소를 기준으로 수열이 두 부분으로 나뉘어지게 되고, 각각이 non-boring이면 전체 수열도 non-boring이다.

4. 이를 재귀적으로 생각한다.

 

그러나 위 접근법을 이용한 풀이를 내려면 수열의 임의의 구간에서 유일한 원소가 존재하는지 판별해야 하는데, 이를 빠르게 할 수 있는 방법이 떠오르지 않았다. 다른 블로그들을 보면 그냥 나이브하게 보되 좌우를 번갈아가면서 유일한 원소를 골라내기만 해도 된다는 풀이가 많은데, 증명이 되어 있는 곳을 찾지 못했고 딱히 증명이 떠오르지도 않았다. 따라서 노선을 틀었고, 내가 해결한 풀이는 다음과 같다.

 

(edit : 이 글을 올리고 얼마 뒤에 songc 형에게 증명을 들었다. 좌우를 번갈아가면서 유일한 원소를 골라낸다면, 해당 구간에 유일한 원소가 존재한다는 가정 하에, 유일한 원소를 찾는 데까지는 양쪽에서부터 구간 크기의 절반 이하로 탐색하게 된다. 어떤 구간에서 해당 원소가 유일한지 확인하는 것은 각 원소별로 등장하는 위치를 vector에 담고 이분 탐색을 하는 등의 방식으로 $O(\log N)$에 구할 수 있다.

 

따라서 수열의 길이가 $N$, 유일한 원소 기준으로 나뉘어진 구간의 크기가 $A \leq B$, 시간복잡도를 $T$라고 하면 $T(N) = $ $T(A)+T(B)+$ $O(A\log N)$이 된다. 귀납적으로 $T(N) = $ $O(N\log ^{2} N)$임을 보이기 위해 $k<N$일 때 $T(k) \leq $ $ck \log^{2} k$이라고 하자. 그러면 $T(N) = $ $T(A)+T(B)+O(A\log N) \leq $ $cA \log^{2} A+cB \log^{2} B + $ $c_{1}A\log N \leq $ $(cA\log A +cB\log B + c_{1}A)\log N$이 된다.

 

$c \geq c_{1}$이라 해도 무방하므로 $T(N) \leq $ $c(A\log A+B \log B +$ $A)\log N = $ $c(A(\log A + 1)+$ $B\log B)\log N = $ $c(A \log 2A +B \log B)\log N$이고, $A \leq B$였으므로 $2A \leq N$이다. 따라서 $T(N) \leq $ $c(A\log N + B \log N)\log N = $ $c(A+B)\log ^{2} N = $ $cN\log^{2}N$이 증명된다.)

 

수열이 non-boring이라면 모든 인덱스 $l$에 대해 $l$로 시작하는 모든 구간에 유일한 원소가 존재해야 한다. 구간 $[l, r]$에 대해 $a$가 유일한 원소라면, $r$은 $l$ 이후에 $a$가 등장하는 첫 번째 위치와 같거나 그보다 뒤, $a$가 등장하는 두 번째 위치보다는 앞이어야 한다. 즉, $l$ 이후에 등장하는 모든 수에 대해 해당 수가 등장하는 첫 번째 위치를 $x$, 두 번째 위치를 $y$라 할 때 $[x, y-1]$에 마킹을 하고, 마킹이 되지 않은 인덱스가 하나라도 존재한다면 수열은 boring이 된다. $l=1$일 때 이 과정은 합 업데이트, 최솟값 쿼리를 지원하는 레이지 세그먼트 트리로 $O(N\log N)$의 시간에 수행 가능하다. $l$을 $l+1$로 늘릴 때는, $l$에 위치했던 수에 대해서만 업데이트를 해주면 되므로 $O(\log N)$의 시간이 걸린다. 따라서 총 시간복잡도 $O(N\log N)$에 해결 가능하다.

 

코드는 다음과 같다.

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

int t, n;
int arr[200005];
int tree[800005];
int lazy[800005];
vector<int> idx;
vector<int> loc[200005];

void init(int node, int s, int e){
    tree[node] = 0;
    lazy[node] = 0;
    if(s==e) return;
    int m = (s+e)>>1;
    init(node<<1, s, m);
    init(node<<1|1, m+1, e);
}

void prop(int node, int s, int e){
    tree[node] += lazy[node];
    if(s^e){
        lazy[node<<1] += lazy[node];
        lazy[node<<1|1] += lazy[node];
    }
    lazy[node] = 0;
}

void update(int node, int s, int e, int l, int r, int v){
    if(l<=s&&e<=r){
        lazy[node] += v;
        prop(node, s, e);
        return;
    }
    prop(node, s, e);
    if(e<l||r<s) return;
    int m = (s+e)>>1;
    update(node<<1, s, m, l, r, v);
    update(node<<1|1, m+1, e, l, r, v);
    tree[node] = min(tree[node<<1], tree[node<<1|1]);
}

int query(int node, int s, int e, int l, int r){
    prop(node, s, e);
    if(e<l||r<s) return 1;
    if(l<=s&&e<=r) return tree[node];
    int m = (s+e)>>1;
    return min(query(node<<1, s, m, l, r), query(node<<1|1, m+1, e, l, r));
}

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        idx.clear();
        for(int i=1;i<=n;i++){
            scanf("%d", &arr[i]);
            idx.push_back(arr[i]);
        }
        sort(idx.begin(), idx.end());
        idx.erase(unique(idx.begin(), idx.end()), idx.end());
        for(int i=1;i<=n;i++) arr[i] = lower_bound(idx.begin(), idx.end(), arr[i])-idx.begin();
        for(int i=0;i<idx.size();i++) loc[i].clear();
        for(int i=1;i<=n;i++) loc[arr[i]].push_back(i);
        for(int i=0;i<idx.size();i++) loc[i].push_back(n+1);
        init(1, 1, n);
        for(int i=0;i<idx.size();i++) update(1, 1, n, loc[i][0], loc[i][1]-1, 1);
        bool o = query(1, 1, n, 1, n);
        for(int i=1;i<n;i++){
            int s = 0;
            int e = loc[arr[i]].size()-1;
            while(s^e){
                int m = (s+e)>>1;
                if(loc[arr[i]][m]>=i) e = m;
                else s = m+1;
            }
            update(1, 1, n, loc[arr[i]][s], loc[arr[i]][s+1]-1, -1);
            if(s+2<loc[arr[i]].size()) update(1, 1, n, loc[arr[i]][s+1], loc[arr[i]][s+2]-1, 1);
            o = o&&query(1, 1, n, i+1, n);
        }
        if(o) printf("non-boring\n");
        else printf("boring\n");
    }
}