[백준 16124] 나는 행복합니다

문제 링크

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

16124번: 나는 행복합니다

 

사용 알고리즘

• 세그먼트 트리(Segment Tree)
• 느리게 갱신되는 세그먼트 트리(Lazy Propagation)
• 세그먼트 트리 비츠(Segment TreeBeats)

 

풀이 과정

처음에는 어떻게 자식노드를 합쳐야 할지를 고민했습니다.

 

제가 생각한 방법은 모듈러 연산의 분배법칙을 이용하는 거였어요.

 

먼저 왼쪽 자식(left)과 오른쪽 자식(right)을 합치는 연산을 다음과 같이 정의합니다.
$$ left * 10^{현재 노드의 범위 / 2} + right $$

하지만 최대로 들어오는 것이 100만 자리이기 때문에

이런 식으로 하면 당연하게도 long long의 범위를 벗어날 것입니다.

 

그래서 모듈러 연산과 모듈러 연산의 분배법칙을 이용해서 위 식을 다음과 같이 변형합니다.

$$ (left * 10^{현재 노드의 범위 / 2} + right) \% MOD $$

$$ (((left \% MOD) * (10^{ 현재 노드의 범위 / 2} \% MOD)) \% MOD + (right \% MOD)) \% MOD $$

저는 이렇게 나온 식을 자식 노드를 합치는 식으로 사용였습니다.

 

다음으로 생각한 것은 1번 쿼리였습니다.

어떻게 해야 특정한 숫자만 바꿀 수 있을지 고민했습니다.

그래서 저는 해당 노드의 값이 from과 같고 모든 자식노드가 모두 같을 때 lazy를 내리는 방식을 생각하였습니다.

이때 모두 자식노드가 같은지 확인하는 방법은 리프 노드에 (1 << 해당 리프 노드의 값)를 추가하여 부모 노드에는 자식 노드의 해당 값을 모두 & 연산한 값을 저장함으로써 확인할 수 있습니다.

이를 tag_condition으로 사용하여 1번 쿼리를 완성하였습니다.

 

다음은 Lazy 연산입니다.

Lazy 연산은 lazy 배열에 값이 있으면 해당 값을 범위의 길이만큼 이어 붙여주는 연산을 수행한 뒤 리프 노드가 아니라면 자식 노드로 내려줍니다.

 

다음은 2번 쿼리입니다.

2번 쿼리는 현재 노드의 범위가 쿼리의 범위 안일 때 현재 노드의 크기를 같이 반환하여 나중에 합칠 때 $10^{반환된 범위}$를 곱해줌으로써 선택된 값들을 합치고, 범위 밖이라면 값을 -1을 반환하여 예외 처리하는 것으로 완성하였습니다.

 

이렇게 해서 제출을 했지만, 시간초과가 떴습니다.

그 이유는 \(10^n\)을 계산할 때 빠른 거듭제곱을 사용한 것이었습니다.

 

이 문제를 해결하기 위해서 반복문을 통해서 미리 다 계산해 놓는 방식을 사용하였습니다.

이렇게 해서 문제를 해결하나 싶었지만 그럼에도 시간 초과가 났습니다.

 

다시 문제의 원인을 찾아보니 1번 쿼리의 시간복잡도가 \(O(NlogN)\)이었습니다.

이 문제는 모든 자식 노드의 값을 or 연산한 결과와 (1 << from)을 & 연산한 결과가 0이면 break 하는 조건을 break_condition으로 추가하여 해결하였습니다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#define MOD 998244353

struct Node {
    ll _and;
    ll _or;
    ull val;
};

struct AtoB {
    ll a, b;
};

struct QR {
    ull val, sz;
};

string n;
ll q, a[1000001];
Node tree[4000001];
vector<AtoB> lz(4000001, {-1, 0});
ll pw[1000001];
ll sm[1000001];

Node f(Node a, Node b, ll sz) {
    return { a._and & b._and, a._or | b._or, ((((a.val % MOD) * pw[sz / 2]) % MOD) + (b.val % MOD)) % MOD };
}

QR qf(QR a, QR b) {
    if (a.val == -1) return b;
    if (b.val == -1) return a;
    return { ((((a.val % MOD) * pw[b.sz]) % MOD) + (b.val % MOD)) % MOD, a.sz + b.sz};
}

Node init(int s, int e, int node) {
    if (s == e) return tree[node] = { 1 << a[s], 1 << a[s], (ull)a[s] };
    int m = s + e >> 1;
    return tree[node] = f(init(s, m, node << 1), init(m + 1, e, node << 1 | 1), (e - s + 1));
}

void lazy(int s, int e, int node) {
    if (lz[node].a == -1) return;

    ll t = ((sm[e - s + 1] % MOD) * lz[node].b) % MOD;
    tree[node] = { 1 << lz[node].b, 1 << lz[node].b, (ull)(t % MOD) };

    if (s != e) {
        lz[node << 1] = lz[node];
        lz[node << 1 | 1] = lz[node];
    }
    lz[node] = { -1, 0 };
}

void update(int s, int e, int node, int l, int r, int from, int to) {
    lazy(s, e, node);
    if (r < s || e < l || !(tree[node]._or & (1 << from))) return;
    if (l <= s && e <= r && tree[node]._and == (1 << from)) {
        lz[node].a = from;
        lz[node].b = to;
        lazy(s, e, node);
        return;
    }
    if (s == e) return;
    int m = s + e >> 1;
    update(s, m, node << 1, l, r, from, to);
    update(m + 1, e, node << 1 | 1, l, r, from, to);
    tree[node] = f(tree[node << 1], tree[node << 1 | 1], e - s + 1);
}

QR query(int s, int e, int node, int l, int r) {
    lazy(s, e, node);
    if (r < s || e < l) return { (ull)-1, 0};
    if (l <= s && e <= r) return { tree[node].val, (ull)(e - s + 1) };
    int m = s + e >> 1;
    return qf(query(s, m, node << 1, l, r), query(m + 1, e, node << 1 | 1, l, r));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> q;
    pw[0] = 1;
    for (int i = 1; i < 1000001; i++) pw[i] = (pw[i - 1] * 10) % MOD;
    for (int i = 1; i < 1000001; i++) sm[i] = ((sm[i - 1] * 10) % MOD + 1) % MOD;
    for (int i = 0; i < n.length(); i++) a[i + 1] = n[i] - '0';

    init(1, n.length(), 1);

    while (q--) {
        int x; cin >> x;
        if (x == 1) {
            int i, j, f, t; cin >> i >> j >> f >> t;
            update(1, n.length(), 1, i, j, f, t);
        }
        else {
            int i, j; cin >> i >> j;
            cout << query(1, n.length(), 1, i, j).val % MOD << '\n';
        }
    }
}