백준16124 나는 행복합니다

작성일 | In

문제 링크

  • http://icpc.me/16124

사용 알고리즘

  • 세그먼트 트리
  • 레이지 프로퍼게이션

시간복잡도

  • $O(Q log N)$

풀이

node가 관리하는 구간에서 a가 b로 바뀌어야 하는 것을 lazy[node][a] = b로 표현해주고, 레이지를 잘 전파해주면 쉽게 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 998244353;

int n, q;
string s;
ll pw[1010101];
ll tree[1 << 21][10];
ll tmp[1 << 21][10];
ll t[10];

void push(int node, int s, int e){
    bool flag = 1;
    for(int i=0; i<10; i++) if(tmp[node][i] != i) flag = 0;
    if(flag) return;
    memset(t, 0, sizeof t);
    for(int i=0; i<10; i++) t[tmp[node][i]] = (t[tmp[node][i]] + tree[node][i]) % mod;
    memcpy(tree[node], t, sizeof t);
    if(s ^ e){
        for(auto ch : {node << 1, node << 1 | 1}){
            for(int i=0; i<10; i++) t[i] = tmp[node][tmp[ch][i]];
            memcpy(tmp[ch], t, sizeof t);
        }
    }
    iota(tmp[node], tmp[node]+10, 0);
}

void update(int l, int r, int a, int b, int node = 1, int s = 1, int e = n){
    push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){
        tmp[node][a] = b; push(node, s, e); return;
    }
    int m = s + e >> 1;
    update(l, r, a, b, node << 1, s, m);
    update(l, r, a, b, node << 1 | 1, m+1, e);
    for(int i=0; i<10; i++){
        tree[node][i] = (pw[e-m] * tree[node << 1][i] + tree[node << 1 | 1][i]) % mod;
    }
}

ll query(int l, int r, int node = 1, int s = 1, int e = n){
    push(node, s, e);
    if(r < s || e < l) return 0;
    if(l <= s && e <= r){
        ll ret = 0; for(int i=0; i<10; i++) ret = (ret + tree[node][i] * i) % mod;
        return ret;
    }
    int m = s + e >> 1;
    ll ret = 0;
    if(m+1 <= r) ret = pw[min(e,r)-m] * query(l, r, node << 1, s, m) + query(l, r, node << 1 | 1, m+1, e);
    else ret = query(l, r, node << 1, s, m);
    ret %= mod;
    return ret;
}

void init(int node = 1, int s = 1, int e = n){
    iota(tmp[node], tmp[node]+10, 0);
    if(s == e){ tree[node][::s[s-1]-'0'] = 1; return; }
    int m = s + e >> 1;
    init(node << 1, s, m);
    init(node << 1 | 1, m+1, e);
    for(int i=0; i<10; i++){
        tree[node][i] = (pw[e-m] * tree[node << 1][i] + tree[node << 1 | 1][i]) % mod;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    pw[0] = 1;
    for(int i=1; i<1010101; i++) pw[i] = pw[i-1] * 10 % mod;
    cin >> s; n = s.size();
    init();
    int q; cin >> q;
    while(q--){
        int op, s, e; cin >> op >> s >> e;
        if(op == 1){
            int a, b; cin >> a >> b; update(s, e, a, b);
        }else{
            cout << query(s, e) << "\n";
        }
    }
}