백준 18277 - Bliski Brojevi (C++)

문제

• 문제 링크

  
   BOJ 18277 - Bliski Brojevi 
  

• 문제 요약

$N$개의 수열과 $Q$개의 쿼리가 주어진다.
각 쿼리마다 주어지는 구간에서의 $l ≤ i < j ≤ r$ 인 $min(|pi - pj|)$ 값을 구해보자.

• 제한

TL : $2$ sec, ML : $512$ MB




$1 ≤ N, Q ≤ 30,000$

알고리즘 분류

• 자료 구조(data structures)
• 세그먼트 트리 (segment tree)
• 오프라인 쿼리(offline_queries)
• mo's(mo's algorithm)

풀이

척 보면 mo's 냄새가 솔솔 난다.

그럼 문제는 결국 현재 관리하는 구간( $[s, e]$ )에서의 $X$ ( $l ≤ i < j ≤ r$ 를 만족하는 $min(|p_i$ - $p_j|)$ ) 를 어떻게 빨리 구할 수 있느냐인데..

"$p_i$는 중복이 없으며 등장하는 수의 범위 역시 $1 ≤ p_i ≤ N$ 를 만족한다." 이 녀석을 이용해보자.

---

$[s, e]$ 의 정보만을 담은 세그먼트 트리에서, 각 노드마다 해당 노드가 관리하는 구간에서의 $X$ 를 들고 있다고 해보자.

그럼 $[s, e]$에 대한 답은 항상 $seg[1]$에 담겨 있게 되고 $[s, e]$ 의 $s$, $e$가 끝점에서 변할 때마다 적절한 업데이트만 취해주면 된다.

중요한 건, 세그에서 관리하고 있는 값은 $[s, e]$ 에 속한 값 뿐이라는 점이다.

---

각 노드마다 앞서 이야기 한 값을 들고 있으려면 다음과 같이 두 개의 추가적인 정보가 필요하다.

• 해당 노드가 담당하는 구간 내 최솟값.
• 해당 노드가 담당하는 구간 내 최댓값.

그럼 노드마다 다음 세가지 값에서의 최솟값이 $X$가 됨을 알 수 있다.

• 왼 쪽 자식 노드의 $X$.
• 오른 쪽 자식 노드의 $X$.
• 오른 쪽 자식 노드의 최솟값 - 왼 쪽 자식 노드의 최댓값.

---

세그가 관리하는 구간은 $1$ ~ $N$이지만 실제 고려해야 하는 값들은 $[s, e]$ 에 실존하는 값 뿐이다.
이 점을 반드시 유의한 채로 업데이트 함수를 짜면 된다.
(나는 고려하지 않아야 하는 노드들에 대해선 모두 $0$으로 기준을 잡아 주었다.)
그렇게 쿼리마다 업데이트를 마친 후 세그의 첫번째 노드에 담긴 $X$값을 취해주면 되겠다.

전체 코드

#include<bits/stdc++.h>
#define N 30001
using namespace std;
 
struct S { int s, e, i = 1e9; }Q[N], seg[1 << 16];
int n, q, i, a[N], an[N];
int s, e, t;
 
S f1(int n, int s, int e, int p, int q)
{
    if (s > p || e < p) return seg[n];
    if (s == e) return seg[n] = { q, q, (int)1e9 };
    int m((s + e) >> 1);
    S L(f1(n << 1, s, m, p, q)), R(f1(n << 1 | 1, m + 1, e, p, q));
    seg[n] = { L.s, R.e, min({L.i, R.i, L.e && R.s ? R.s - L.e : (int)1e9}) };
    if (!seg[n].s) seg[n].s = R.s;
    if (!seg[n].e) seg[n].e = L.e;
    return seg[n];
}
void in()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (i = 1; i <= n; cin >> a[i++]);
    for (i = 0; i < q; i++)
        cin >> Q[i].s >> Q[i].e, Q[i].i = i;
}
void sv()
{
    sort(Q, Q + q, [](S x, S y)
        {
            x.s /= 300, y.s /= 300;
            return x.s ^ y.s ? x.s < y.s : x.e < y.e;
        });
    for (i = 0; i < q; i++)
    {
        while (s > Q[i].s) s--, f1(1, 1, n, a[s], a[s]);
        while (e < Q[i].e) e++, f1(1, 1, n, a[e], a[e]);
        while (s < Q[i].s) f1(1, 1, n, a[s], 0), s++;
        while (e > Q[i].e) f1(1, 1, n, a[e], 0), e--;
        an[Q[i].i] = seg[1].i;
    }
    for (i = 0; i < q; cout << an[i++] << '\n');
}
int main()
{
    in();
    sv();
}

comment

대충 $O(Q * √N * logN)$ 정도 일 거 같고
범위가 작아 이 정도로 상수 차이가 크게 날 줄 몰랐는데, 재귀 세그로 AC 받기가 살짝 빡빡하다.

TLE 한 번 맞고 1912ms로 처음 AC를 띄운 뒤, 이것 저것 건드리며 1616ms까지 줄여보긴 했지만

N ≤ 3e4 가 재귀 세그로 타협 가능한 마지노선 범위였는 듯 하다. 비재귀 세그로 짜면 좀 더 널널하게 될 듯.