백준 31222 - 수열과 어렵지 않은 쿼리 (C++)

문제

• 문제 링크

  
   BOJ 31222 - 수열과 어렵지 않은 쿼리 
  

• 문제 요약

길이 $n$의 수열 $A_1, A_2, ... , A_n$에 대해 임의의 연속 부분 수열 $[a_l, a_{l+1}, ... , a_{r-1}, a_r]$에서 모든 원소가 서로 일치할 때, 이러한 구간 $[l, r]$을 '연속 일치 구간'이라고 한다.
또한 임의의 연속 일치 구간이 수열의 다른 연속 일치 구간에도 완전히 포함되지 않는다면 이를 '중요한 연속 일치 구간'이라고 한다. 이때, 아래 쿼리를 수행하는 프로그램을 작성하자.



$1$ $i$ $x$ : $A_i$의 값을 $x$로 변경한다. $(1 ≤ i, x ≤ n)$

$2$ $l$ $r$ : $[l, r]$에서 서로 다른 중요한 연속 일치 구간의 개수를 출력한다. $(1 ≤ l ≤ r ≤ n)$




• 제한

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




$1 ≤ n, q ≤ 2 \times 10^5$

$1 ≤ A_i ≤ n$

알고리즘 분류

• 자료 구조 (Data Structures)
• 세그먼트 트리 (Segment Tree)

풀이

다양한 풀이가 존재해 보이는데, 직관적으로 떠오른 건 세그먼트 트리에서 $3$개의 값을 관리하는 것이었다.

구체적으로 노드 하나가 $[l, r]$을 담당할 때 $\{A_l, A_r, cnt\}$의 형태로 관리해주는 것이다. $cnt$는 중요한 연속 일치 구간의 수이다.

그렇다면 다음으로 생각해야 할 것은 두 구간의 $merge$를 알맞게 처리하는 것이다. $[l_1, r_1], [l_2, r_2]$를 관리하는 두 노드가 $merge$될 때, $A_{r_1}$과 $A_{l_2}$가 같은 값인 경우만 잘 잡아주면 된다.

임의의 구간의 답을 얻는 쿼리를 처리할 때, 유효한 구간을 벗어나는 구간을 답에 포함하지 않도록 적절히 일반화 해주어야 한다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
struct T{ int l, r, cnt; } seg[1 << 19];
 
T merge(T x, T y)
{
    if(!x.l || !y.l) return x.l ? x : y;
    T res{x.l, y.r, x.cnt + y.cnt - (x.r == y.l)};
    return res;
}
T update(int n, int s, int e, int i, int v)
{
    if(s > i || e < i) return seg[n];
    if(s == e)
    {
        seg[n].l = seg[n].r = v;
        seg[n].cnt = 1;
        return seg[n];
    }
    int m(s + e >> 1);
    T l(update(n << 1, s, m, i, v));
    T r(update(n << 1 | 1, m + 1, e, i, v));
 
    return seg[n] = merge(l, r);
}
T query(int n, int s, int e, int l, int r)
{
    if(s > r || e < l) return T{};
    if(s >= l && e <= r) return seg[n];
    int m(s + e >> 1);
    return merge(query(n << 1, s, m, l, r), query(n << 1 | 1, m + 1, e, l, r));
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
 
    for(int i(1); i <= n; i++)
    {
        int val; cin >> val;
        update(1, 1, n, i, val);
    }
    while(q--)
    {
        int op, x, y; cin >> op >> x >> y;
        if(op & 1) update(1, 1, n, x, y);
        else cout << query(1, 1, n, x, y).cnt << '\n';
    }
}

comment

풀고 보니까 살짝 어렵게 푼 것 같기도 한데, 다른 쉬운 풀이들이 여럿 존재할 것 같다.