https://www.acmicpc.net/problem/3002
접근법
- 구간합을 저장하는 세그먼트 트리 + 구간 업데이트를 위한 lazy propagtion으로 접근하면 진행이 잘 안됨
- 9 -> 0 이 되는 처리를 어떻게 할 것인가...
- 9로 된 것들만 처리를 해본다면.....counting???
- 0 ~ 9를 counting 하는 세그먼트 트리
- 구간 업데이트는 counting이 shifting 되는 것으로 처리
- 구간의 합은 counting 정보를 알면 계산 가능
- logN x 10 x M 정도의 시간 복잡도
newbieski