BOJ 24506 | blobpopcorn

아이디어성 문제라고 생각했는데 구현도 헷갈리고 어려웠습니다. 중간에 LIS라고 착각해서 이상한 길로 빠지기도 하고, 어떻게든 해설은 안 보려고 했지만 결국 멘붕와서 해설을 보게 만들었던 문제...

아무튼 기본 아이디어는 스스로 떠올렸기 때문에 그나마 만족합니다.

일단 이 문제를 푸는 방법은 여러 가지가 있겠지만 저는 세그 트리로 풀었습니다.

풀이 과정

어떤 블롭 $A_i$와 $A_j$가 그 사이에 있는 모든 블롭보다 크다면 $(i, j)$를 구경 블롭 쌍이라고 하겠습니다.

우리는 이 구경 블롭 쌍이 총 몇개인지 세어야 합니다.

커여운 블롭들이 이렇게 놓여 있다고 생각해 보겠습니다.

가운데에서 빛나는 파란색 슈-퍼 블롭에 대해 한번 생각해봅시다.
이 블롭이 작은 구경 블롭이 될 수 있는 경우의 수는 몇 가지일까요?

바로 2가지입니다.
파랑 블롭은 주황색으로 표시한 블롭들과 짝을 이뤄야만 작은 구경 블롭이 될 수 있습니다.

여기서 포인트는, 어떠한 경우에도 블롭 하나가 3개 이상의 작은 구경 블롭이 될 수 없다는 점입니다.

주황색 블롭 이외에 큰 구경 블롭이 되어 줄 블롭을 찾으려면, 주황색 블롭 바깥으로 가야 하는데 그랬다가는 정작 파랑 블롭이 주황 블롭을 구경하지 못하게 되어 구경 블롭 쌍을 이룰 수 없습니다.

따라서 모든 블롭에 대해 이 블롭이 작은 구경 블롭이 될 수 있는 경우의 수는 0, 1, 2 중에서 나오고, 이 경우의 수들의 합이 구경 블롭 쌍의 개수가 됩니다.

블롭이 큰 구경 블롭이 되는 경우는 신경쓰지 않아도 되는게, 어떤 블롭이 큰 구경 블롭이면 그 짝인 블롭은 작은 구경 블롭이라 자동적으로 카운트되기 때문입니다. 카운트되지 않는 블롭 쌍은 (큰 구경 블롭, 큰 구경 블롭) 일텐데 그런 쌍은 없습니다.

이렇게 $N$개의 블롭 중에서 구경 블롭 쌍의 개수는 최대 $2N$개라는 사실을 생각해볼 수 있습니다.

이제 작은 구경 블롭이 2번 되지 못하는 블롭들을 찾아내면 $2N$에서 그 수를 빼서 정답을 도출해낼 수 있습니다.

대상 블롭의 왼쪽에서 큰 구경 블롭이 되어 줄 수 있는 블롭을 $L$-블롭,
오른쪽에서 큰 구경 블롭이 되어 줄 수 있는 블롭을 $G$-블롭 이라고 하겠습니다.

$L$-블롭이나 $G$-블롭은 대상 블롭에서 양쪽으로 뻗어나가면서 가장 먼저 찾게 되는 대상 블롭보다 큰 블롭이 됩니다.

$L$-블롭이 없는 블롭들을 생각해봅시다.

우선 가장 왼쪽 블롭은 $L$-블롭이 없습니다. 당연하겠죠?

그리고 첫 번째 블롭보다 큰 이 블롭도 $L$-블롭이 없습니다.

그리고 방금 찾은 블롭보다 큰 이 블롭 ( 똑같아 보여도 그냥 크다고 합시다 ) 도 $L$-블롭이 없습니다.

$L$-블롭이 없으려면, 그 블롭 왼쪽에 자신보다 큰 블롭이 없으면 됩니다.

이 블롭들은 증가하는 부분수열을 이룹니다.
저 블롭들의 높이를 5 3 6 1 2 7 4 라고 하면,
$L$-블롭이 없는 블롭들의 높이는 5 6 7 입니다.

그러나 항상 $LIS$를 이루지는 않고, 여기서는 그리디하게 증가하는 부분수열이라고 하겠습니다. 이름 그대로 생각하면 편합니다.

$G$-블롭이 없는 블롭은 블롭들의 순서를 reverse 해서 구하면 됩니다.

이 그리디하게 증가하는 부분수열의 개수를 구할 수 있다면, 구경 블롭 쌍의 개수를 구할 수 있습니다.

정확히는 $2N -$ ($L$-블롭 없는 블롭들 개수) $-$ ($G$-블롭 없는 블롭들 개수) 개가 됩니다.

이제 그리디하게 증가하는 부분수열을 세그먼트 트리를 이용해서 업데이트 해주면서 길이를 $O(1)$에 구하면 됩니다!

세그먼트 트리

각 노드에는 len, maxvalue를 담은 구조체를 넣습니다.
len은 구간의 그리디하게 증가하는 부분수열 길이이고, maxvalue는 그 수열의 최댓값입니다.

세그트리의 init()은 left 노드에서 구한 그리디하게 증가하는 부분수열과, right 노드에서 구한 그리디하게 증가하는 부분수열을 합쳐서 현재 노드에 넣는 방법으로 진행합니다.

left 노드에 있던 그리디하게 증가하는 부분수열이 right 노드의 수열과 합쳐지려면 right 노드의 앞 부분을 어느 정도 잘라낼 필요가 있습니다.

left에서 $[1, 2, 4, 7, 8]$을 가져왔고, right에서 $[3, 5, 9, 10, 12]$를 가져왔다면 right의 3과 5는 버려야 두 수열을 합칠 수 있습니다.

따라서 right 수열의 원소 중 left 수열의 최댓값보다 큰 값의 개수를 구해야 합니다. 이 개수를 K라고 합시다.

그러면 현재 노드를 { (left 수열의 길이) + K, max(left.max, right.max) } 로 구할 수 있습니다.

이 전략은 update()에도 사용할 수 있습니다.

다만 left.max보다 큰 right 수열의 원소 개수를 구하는 작업이 $O(N)$에 진행되면 시간초과가 나므로 이 부분에서 주의가 필요합니다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long

#define debug if constexpr (local) std::cout
#define endl '\n'

struct Node {
    ll len;
    ll mxv;
};

class SegTree {
private:
    vector<Node> tree;

public:
    SegTree(ll N) {
        tree.resize(N * 4);
    }

    void Print() { // debugging
        for (auto& i : tree)
            debug << i.len << ' ';
        debug << endl;
    }

    Node init(vector<ll>& nums, ll node, ll s, ll e) {
        // leaf node => len=1, maxvalue=value
        if (s == e)
            return tree[node] = {1, nums[s]};

        Node lnode = init(nums, node * 2, s, (s + e) / 2);
        Node rnode = init(nums, node * 2 + 1, (s + e) / 2 + 1, e);

        ll n = lnode.len;
        ll k = find(lnode.mxv, node * 2 + 1, (s + e) / 2 + 1, e, (s + e) / 2 + 1, e).len;

        //debug << "tree[" << node << "] s : " << s << " e : " << e << " len : " << n+k << " mxv : " << max(lnode.mxv, rnode.mxv) << endl;

        return tree[node] = {n + k, max(lnode.mxv, rnode.mxv)};
    }

    Node update(ll node, ll s, ll e, ll idx, ll value) {
        // Bottom-up
        if (idx < s || e < idx)
            return tree[node];

        // leaf node
        if (s == e)
            return tree[node] = {1, value};

        Node lnode = update(node * 2, s, (s + e) / 2, idx, value);
        Node rnode = update(node * 2 + 1, (s + e) / 2 + 1, e, idx, value);

        ll n = lnode.len;
        ll k = find(lnode.mxv, node * 2 + 1, (s + e) / 2 + 1, e, (s + e) / 2 + 1, e).len;

        return tree[node] = {n + k, max(lnode.mxv, rnode.mxv)};
    }

    Node find(ll atleast, ll node, ll s, ll e, ll l, ll r) {
        if (r < s || e < l)
            return {0, tree[node].mxv};

        if (s == e) {
            if (tree[node].mxv > atleast)
                return {1, tree[node].mxv};
            else
                return {0, tree[node].mxv};
        }

        // not leaf node && less than atleast
        if (tree[node].mxv <= atleast)
            return {0, tree[node].mxv};

        
		Node left = find( atleast, node * 2, s, (s + e) / 2, l, r);
		
		//If no change => break
		if (left.len == tree[node*2].len) return tree[node];
		
		Node right = find( max(atleast, left.mxv), node * 2 + 1, (s + e) / 2 + 1, e, l, r);
        return {left.len+right.len, max(left.mxv, right.mxv)};
    }

    ll query() {
        return tree[1].len;
    }
};


int main() {
    FASTIO;
    ll N, Q;
    cin >> N >> Q;
    vector<ll> nums;
    vector<ll> rnums;
    nums.push_back(0);
    for (ll i = 0; i < N; i++) {
        ll t;
        cin >> t;
        nums.push_back(t);
        rnums.push_back(t);
    }
    rnums.push_back(0);
    reverse(rnums.begin(), rnums.end());

    SegTree SG(N);
    SegTree SG_R(N);
    SG.init(nums, 1, 1, N);
    SG_R.init(rnums, 1, 1, N);

    for (ll i = 0; i < Q; i++) {
        ll o;
        cin >> o;
        if (o == 1) {
            ll x, y;
            cin >> x >> y;
            SG.update(1, 1, N, x, y);
            SG_R.update(1, 1, N, (N - x + 1), y);
        } else {
            cout << 2 * N - SG.query() - SG_R.query() << endl;
        }
    }
    return 0;
}