BOJ 3408 - Non-boring sequences

문제 링크 : www.acmicpc.net/problem/3408

문제 힌트

1. 모든 부분 배열에 대해서 non-boring 한지 확인할 수 있을까?

2. 모든 non-boring 한 배열에는 unique한 원소가 존재한다.

3. unique 한 원소를 포함한 모든 부분 배열은 non-boring 하다.

4. 순서를 잘 바꿈으로써 시간 복잡도를 만족시킬 수 있다.

문제 풀이

-스포 주의-

우리의 목표는 모든 부분 배열에 대해서 그 부분 배열이  non-boring 한지를 알아내는 것이다. 이에 앞서 우리는 모든 원소에 대해서 그 원소와 같은 값을 가지는 바로 왼쪽 원소와 오른쪽 원소의 위치를 모든 원소에 대해서 저장하고 있을 것이다.

첫번째로 구간을 배열 전체로 설정하자. 이 배열이 non-boring 하기 위해서는 이 중 unique한 원소가 있어야 할 것이다. 그리고 그 unique 한 원소를 포함하는 모든 부분배열은 non-boring 하다. 따라서 그 원소를 기준으로 전체 배열을 구간으로 나누어버릴 수 있다.

이를 나누어진 구간에서 계속해서 반복하여, 구간의 크기가 1일때까지 하면 된다. 그 전에 unique한 원소가 존재하지 않으면, 배열은 boring한 배열이다. 

이 과정에서 가장 중요한 것은 unique 한 원소를 찾는 순서이다. 만약 앞에서부터 순서대로 그 원소가 unqiue한지를 판별한다면 unique 한 원소가 계속 뒤쪽에 있는 경우에 배열의 구간도 한쪽으로 치우쳐지게 되기 때문에 $O(N^2)$의 시간복잡도가 나오게 된다. 

이 문제를 해결하기 위해서 unqiue 한 원소를 구간의 바깥에서 부터 확인하는 것으로 바꾼다. 즉 [s,e]구간이 있을 때, s,e,s+1,e-1... 순서로 확인을 하는 것이다. 

 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
 
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
 
ll arr[1010101];
vector<ll> v;
bool ans=0;
ll cnt[202020];
ll l[1010101];
ll r[1010101];
 
void sol(ll s,ll e){
    //printf("%lld %lld\n",s,e);
    if(s>=e) return;
    if(ans) return;
    ll mid=(s+e)/2;
    ll x=0;
    ll i;
    for(x=0;x<=(e-s)/2;x++){
        i=s+x;
        if(l[i]<s&&r[i]>e){
            sol(s,i-1);
            sol(i+1,e);
            return;
        }
        i=e-x;
        if(l[i]<s&&r[i]>e){
            sol(s,i-1);
            sol(i+1,e);
            return;
        }
    }
    ans=1;
    return;
}
 
vector<ll> v2[1010101];
 
int main(){
    ll t;
    scanf("%lld",&t);
    while(t--){
        ans=0;
        v.clear();
        ll i,j,k,m,n;
        scanf("%lld",&n);
        for(i=1;i<=n;i++){
            scanf("%lld",&arr[i]);
            v.push_back(arr[i]);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()),v.end());
        for(i=1;i<=n;i++)
            arr[i]=lower_bound(v.begin(), v.end(),arr[i])-v.begin()+1;
 
        for(i=0;i<=n;i++){
            l[i]=0;
            r[i]=n+1;
            v2[i].clear();
            v2[i].pb(0);
        }
        for(i=1;i<=n;i++)
            v2[arr[i]].pb(i);
        for(i=0;i<=n;i++)
            v2[i].pb(n+1);
 
        for(i=0;i<=n;i++)
            for(j=1;j<v2[i].size();j++){
                l[v2[i][j]]=v2[i][j-1];
                r[v2[i][j-1]]=v2[i][j];
            }
        
        //for(i=1;i<=n;i++)
        //    printf("%lld %lld %lld\n",i,l[i],r[i]);
 
        sol(1,n);
        if(ans) printf("boring\n");
        else printf("non-boring\n");
    }
}