BOJ 16124 - 나는 행복합니다

HeeJaYaa님의 추천으로 Class 9 문제들을 풀고 있다. Class 9 문제들은 인터넷에 풀이가 많지 않은 경우가 꽤 있어 푸는대로 풀이를 작성해보려 한다. 원래 어제부터 풀고 싶던 문제는 https://www.acmicpc.net/problem/9244 인데, 하루동안 생각해도 모르겠어서 넘어왔다. 혹시 저 문제 푸신 분 있으면 힌트 부탁드립니다..

 

문제 요약

 

숫자로 이루어진 문자열이 주어질 때, 다음과 같은 두 쿼리를 처리해야 한다.

1번 쿼리 : 구간 \([l, r]\)에 위치한 숫자 \(x\)를 모두 \(y\)로 바꾼다.

2번 쿼리 : 구간 \([l,r]\)을 읽은 수를 998244353으로 나눈 나머지를 출력한다.

 

풀이

일단 업데이트 쿼리가 없다고 생각해보자. 그러면 세그트리의 각 노드에 합을 저장하고, 두 노드를 합칠 때 앞 노드의 값에 뒤 노드의 길이만큼 10을 곱해 더해주면 된다. 그런데 그냥 합을 저장하면 업데이트 처리가 어려울 것 같으니 각 숫자 별로 합에 기여하는 만큼을 저장해주자. 실제 값은 이 값에 숫자를 곱해 모두 더해주면 된다.

 

이제 업데이트를 해야 하는데, 이 부분이 어렵다. \(lazy[idx][x]\)를 \(x\)가 가야 하는 숫자라고 정의하자. 기본값은 당연히 \(x\)이다. 노드 자신에서의 업데이트는 \(tree[idx][x]\)값을 \(tree[idx][y]\)에 더해주는 식으로 구현하면 되는데, 자식으로의 전파가 굉장히 까다롭다. 

 

관리를 쉽게 하기 위해, 모든 숫자에서 lazy를 한 번만 따라가도 되는 상태로 유지하자. 이를 위해서는, \(lazy[idx][x]=y\)를 할 때 \(lazy[idx][i]=x\)였던 모든 \(i\)도 같이 갱신해주면 된다. (마치 Union-Find의 Path Compression과 같다)

 

이러면 각 \(x\)에 대해서 \(lazy[ch][x]\)가 가야할 값은  \(lazy[idx][lazy[ch][x]]\)이다. 이를 propagation 시에 적용해주면 된다. 구현적으로 약간 까다로운 부분들이 있으니 조심하면서 짜주면 AC를 받을 수 있다.