백준 2849 - 탭댄스 (C++)

문제

• 문제 링크

  
   BOJ 2849 - 탭댄스 
  

• 문제 요약

탭댄스의 안무는 $L$과 $R$로 이루어진 수열로 표현될 수 있다.
안무의 점수는 $L$과 $R$이 두 번 연속해서 나오지 않는 연속된 원소들로 이루어진 가장 긴 부분 수열의 길이로 정의된다.

$Q$번의 안무가 수정될 때마다, 해당 순간의 안무의 점수를 출력하자.

• 제한

TL : $1$ sec, ML : $128$ MB




$1 ≤ N, Q ≤ 200,000$

가장 처음의 안무는 $L$로만 이루어져 있다.

알고리즘 분류

• 자료 구조 (data_structures)
• 세그먼트 트리 (segment tree)

풀이

BOJ 16993 - 연속합과 쿼리 와 같은 문제들을 푼 경험이 있다면 그리 어렵지 않게 문제를 풀 수 있다.

나는 세그먼트 트리의 구조체 노드에서, $5$개의 값을 관리하였는데 각각의 의미는 다음과 같다.

$ans$ : 해당 노드가 관리하는 구간에서의 답.

$pre$ : 해당 노드가 관리하는 구간에서의 최장 접두사.

$suf$ : 해당 노드가 관리하는 구간에서의 최장 접미사.

$st$ : 해당 노드가 관리하는 구간을 $[s, e]$라 할 때, $s$번째 안무.

$ed$ : 해당 노드가 관리하는 구간을 $[s, e]$라 할 때, $e$번째 안무.

$pre$와 $suf$는 답에 포함될 가능성이 있는 후보군이기 때문에, 이들을 계산할 때에도 두 안무가 인접하면 안된다는 조건을 지켜야 한다.

---

어떤 두 구간 $l$, $r$이 $merge$된다고 가정해보자.

이들이 $merge$된 결과를 $res$에 담으려할 때 각 값들이 어떻게 변화하는지, 무엇을 고려해야 하는지 생각해보자.

바로 보이는 것은, $l.ed$와 $r.st$가 같다면 두 구간은 $merge$ 될 수 없다는 사실이다.
이 때의 $res$가 가져가야할 값들은 단순하므로 설명 생략.

이제 두 구간이 $merge$ 될 수 있을 때를 생각해보자.
이 경우 $res$의 $default$값에서 변할 가능성이 있는 후보군들은 $ans, pre, suf$가 되겠다.

$res.pre$ : $l.pre$가 곧 $l$의 전체 길이와 같다면, $r.pre$를 더해줄 수 있다.

$res.suf$ : $r.suf$가 곧 $r$의 전체 길이와 같다면, $l.suf$를 더해줄 수 있다.

$res.ans$ : $l.suf$와 $r.pre$의 합이 답이될 수 있다.

이 정보들을 토대로 업데이트 함수를 구성하고, 세그먼트 트리의 첫 번째 노드에 기록된 $ans$를 매번 출력해주면 쿼리당 $O(logN)$에 문제를 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
struct Node
{
    int ans, pre, suf;
    char st, ed;
} seg[1 << 19];
bitset <200001> arr;
 
Node Merge(const Node& l, const Node& r, int len_l, int len_r)
{
    Node res({ 1, l.pre, r.suf, l.st, r.ed });
    if (l.ed ^ r.st)
    {
        if (len_l == l.pre) res.pre += r.pre;
        if (len_r == r.suf) res.suf += l.suf;
        res.ans = l.suf + r.pre;
    }
    res.ans = max({ res.ans, l.ans, r.ans, res.pre, res.suf });
    return res;
}
Node Update(int n, int s, int e, int i)
{
    if (s > i || e < i) return seg[n];
    if (s == e) return seg[n] = { 1, 1, 1, arr[i], arr[i] };
    int m(s + e >> 1);
    return seg[n] = Merge(Update(n << 1, s, m, i), Update(n << 1 | 1, m + 1, e, i), m - s + 1, e - m);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
 
    for (int i(1); i <= n; Update(1, 1, n, i++));
    for (int x; q--;)
    {
        cin >> x; arr[x] = arr[x] ^ 1;
        Update(1, 1, n, x);
        cout << seg[1].ans << '\n';
    }
}

comment

끝