취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3002번 문제인 아날로그 다이얼이다.
문제는 아래 링크를 확인하자.

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

한 자리 수가 저장되어있는 배열에서, [L,R]의 숫자들의 합을 출력하고 해당 범위의 숫자들에 각각 1을 더하는(단, 10이 될 경우 값을 0으로 설정한다) 시행을 반복하는 문제이다.

9에 1을 더하면 10 대신 0이 되어야 한다는 조건이 없다면 lazy propagation이 적용된 구간합 세그먼트트리로 문제를 해결할 수 있을 것이다. 이 문제는 9에 1을 더하면 10이 아닌 0이 되어야 하므로 해당 범위에 있는 9의 개수를 별도로 관리해주는 방식으로 문제를 해결해야 할 것 같다. 이 때 1을 더해 9가 되는 수가 몇 개나 있는지를 알 수 없다면 9의 개수를 갱신하며 관리하기 어려울 것이다. 따라서 이와 같은 방향의 구현을 하려면 9의 개수뿐만이 아닌 음이 아닌 한자리 정수 각각을 모두 관리해야 할 것이다.

따라서, 대응되는 노드별로 "음이 아닌 한자리 정수 각각"의 개수, 즉 노드마다 10개의 정수를 관리하는 lazy propagation이 적용된 세그먼트트리를 구현하는 것으로 문제를 해결할 수 있다. 남은 건 구현이다!

propagation이 필요한 시점이 언제인지에 유의하며 구현하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int N, M;
string s;
int seg[524288][10];
int lazy[524288];

void init(int L, int R, int sI) {
	if (L == R) {
		seg[sI][s[L - 1] - '0'] = 1;
		return;
	}

	int l = sI * 2, r = sI * 2 + 1;
	init(L, (L + R) / 2, l), init((L + R) / 2 + 1, R, r);
	for (int i = 0; i < 10; i++) seg[sI][i] = seg[l][i] + seg[r][i];
}

void propagate(bool isLeaf, int sI) {
	int arr[10] = { 0,0,0,0,0,0,0,0,0,0 };

	for (int i = 0; i < 10; i++) arr[(i + lazy[sI]) % 10] = seg[sI][i];
	for (int i = 0; i < 10; i++) seg[sI][i] = arr[i];
	
	if (!isLeaf) lazy[sI * 2] += lazy[sI], lazy[sI * 2 + 1] += lazy[sI];
	
	lazy[sI] = 0;
}

int query(int L, int R, int qL, int qR, int sI) {
	if (lazy[sI]) propagate(L == R, sI);
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) {
		lazy[sI]++;
		int ret = 0;
		for (int i = 0; i < 10; i++) ret += i * seg[sI][i];
		propagate(L == R, sI);
		return ret;
	}

	int ret = query(L, (L + R) / 2, qL, qR, sI * 2) + query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);

	for (int i = 0; i < 10; i++) seg[sI][i] = seg[sI * 2][i] + seg[sI * 2 + 1][i];
	
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> s;
	
	init(1, N, 1);

	while (M--) {
		int L, R; cin >> L >> R;
		cout << query(1, N, L, R, 1) << '\n';
	}
}