3408번: Non-boring sequences

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

[l, r] 구간에서 단 한번만 나오는 수를 x라 하고 i번째에 위치한다고 하자. 만약 이러한 수가 없다면 boring이다.
l<=l1, r1<=r 인 [l1,r1] 구간이 x를 포함하면 해당 구간은 non-boring 수열일 것이다.
정리해서 다음과 같은 조건 중 하나라도 만족하면 해당 구간은 boring 수열을 갖고 있다.
1. 해당 구간에 한번만 나오는 수가 없다.
2. [l,i-1]에 boring 수열이 존재한다.
3. [i+1,r]에 boring 수열이 존재한다.

이제 i를 어떻게 효율적으로 잡는지가 문제이다.
먼저, 사전에 각 수마다 양쪽에 값이 같은 수의 위치를 저장해놓는다. 이를 통해 [l,r] 구간에 존재하는 x가 해당 구간에서 하나만 존재하는지 확인할 수 있다.
[l,r]구간에서 왼쪽에서부터 오른쪽으로 수를 하나씩 확인하며 i를 결정하면 $O(n^2)$의 시간복잡도에 해결할 수 있다.
그런데 왼쪽과 오른쪽을 번갈아 수를 하나씩 확인하며 i를 결정하면 $O(n\lg n)$에 가능하다. 이건 확인했던 부분 크기와 재귀호출 깊이를 생각하면 쉽게 알 수 있을듯 싶다.

시간복잡도는 테스트케이스마다 $O(n\lg n)$

#include<cstdio>
#include<map>
using namespace std;
int t, n, prv[200001], nxt[200001];
int f(int l, int r) {
    if (r < l) return 1;
    for (int i = l, j = r; i <= j; i++, j--) {
        if (prv[i] < l && r < nxt[i]) return f(l, i - 1)&f(i + 1, r);
        if (prv[j] < l && r < nxt[j]) return f(l, j - 1)&f(j + 1, r);
    }
    return 0;
}
void solve() {
    scanf("%d", &n);
    map<int, int> idx;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        prv[i] = idx[x];
        idx[x] = nxt[idx[x]] = i;
        nxt[i] = n + 1;
    }
    puts(f(1, n) ? "non-boring" : "boring");
}
int main() {
    for (scanf("%d", &t); t--;) solve();
    return 0;
}