[ BOJ ] 3002 : 아날로그 다이얼 ( PLATINUM 2 ) / C

문제

아날로그 다이얼이란 0부터 9까지 각 숫자 중 하나를 항상 표시하고 있는 작은 기계이다. 다이얼에는 화면에 보이는 숫자를 1 증가시킬 수 있는 버튼도 있다. (9를 1 증가시키면 0이 된다)

상근이는 이러한 아날로그 다이얼을 N개 가지고 있고, 모두 책상에 일렬로 올려 놓았다. 왼쪽 기계부터 1번기계이며, 가장 오른쪽 기계는 N번 기계이다. 또, 기계의 앞에 무엇인가를 작성할 수 있도록 종이 두 장을 놓았다.

가장 처음에 상근이는 다이얼에 보이는 숫자를 첫 번째 종이에 적는다. 그 다음 다음과 같은 행동을 M번 반복한다.

1. 두 정수 A와 B를 고른 다음, 첫 번째 종이에 작성한다. (1 ≤ A ≤ B ≤ N)

2. A번째 다이얼부터 B번째 다이얼에 적혀있는 숫자의 합을 구한 다음에 두 번째 종이에 작성한다.

3. A번째부터 B번째 다이얼의 버튼을 한 번씩 누른다.

상근이는 위와 같은 게임(?)을 모두 완료했다. 하지만, 갑자기 벽에서 정인이가 튀어나왔고, 두 번째 종이와 다이얼 N개를 모두 들고 군대로 도망가버렸다.

상근이는 첫 번째 종이만 가지고 있다. 두 번째 종이에 쓰여 있는 수를 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 250,000, 1 ≤ M ≤ 100,000)

둘째 줄에는 가장 처음에 다이얼에 표시된 숫자가 주어진다. 이 숫자는 공백없이 주어진다.

다음 M개 줄에는 상근이가 고른 숫자인 A와 B가 주어진다. (1 ≤ A ≤ B ≤ N)

출력

출력은 총 M개 줄이다. 상근이가 구한 다이얼의 합을 순서대로 출력한다.

풀이 과정

일의 자리 수를 모아놓은 counts 배열이 있는 Node를 선언하여 sum과 함께 관리했다. 이를 레이지 세그먼트 트리로 구현하였다.

#include <stdio.h>
#define SIZE 250001
typedef long long LL;

char str[SIZE];
int arr[SIZE];
typedef struct _Node {
	LL sums;
	int counts[10];
	LL lazy;
} Node;
Node tree[SIZE * 4];

Node merge(Node a, Node b) {
	Node tmp;

	tmp.sums = a.sums + b.sums;
	for (int i = 0; i < 10; i++) tmp.counts[i] = a.counts[i] + b.counts[i];
	tmp.lazy = 0;

	return tmp;
}

void init(int start, int end, int idx) {
	if (start == end) {
		for (int i = 0; i < 10; i++) tree[idx].counts[i] = 0;
		tree[idx].counts[arr[start]] = 1;
		tree[idx].sums = arr[start];
		tree[idx].lazy = 0;
		return;
	}

	int mid = (start + end) / 2;
	init(start, mid, idx * 2);
	init(mid + 1, end, idx * 2 + 1);
	tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
}

void push(int start, int end, int idx) {
	if (tree[idx].lazy != 0) {
		LL new_sums = 0;
		int new_counts[10];
		for (int i = 0; i < 10; i++) {
			new_sums += tree[idx].counts[i] * ((i + tree[idx].lazy) % 10);
			new_counts[((i + tree[idx].lazy) % 10)] = tree[idx].counts[i];
		}

		tree[idx].sums = new_sums;
		for (int i = 0; i < 10; i++) tree[idx].counts[i] = new_counts[i];

		if (start != end) {
			tree[idx * 2].lazy += tree[idx].lazy;
			tree[idx * 2 + 1].lazy += tree[idx].lazy;
		}

		tree[idx].lazy = 0;
	}
}

Node interval_sum(int start, int end, int idx, int left, int right) {
	Node tmp;
	tmp.sums = -1;
	for (int i = 0; i < 10; i++) tmp.counts[i] = 0;
	tmp.lazy = 0;

	push(start, end, idx);
	if (end < left || right < start) return tmp;
	if (left <= start && end <= right) return tree[idx];

	int mid = (start + end) / 2;
	Node q1 = interval_sum(start, mid, idx * 2, left, right);
	Node q2 = interval_sum(mid + 1, end, idx * 2 + 1, left, right);
	if (q1.sums < 0 || q2.sums < 0) {
		if (q1.sums >= 0) return q1;
		else return q2;
	}

	tmp = merge(q1, q2);
	return tmp;
}

void interval_inc(int start, int end, int idx, int left, int right) {
	push(start, end, idx);
	if (end < left || right < start) return;
	if (left <= start && end <= right) {
		LL new_sums = 0;
		int new_counts[10];
		for (int i = 0; i < 10; i++) {
			new_sums += tree[idx].counts[i] * ((i + 1) % 10);
			new_counts[((i + 1) % 10)] = tree[idx].counts[i];
		}

		tree[idx].sums = new_sums;
		for (int i = 0; i < 10; i++) tree[idx].counts[i] = new_counts[i];

		if (start != end) {
			tree[idx * 2].lazy += 1;
			tree[idx * 2 + 1].lazy += 1;
		}

		return;
	}

	int mid = (start + end) / 2;
	interval_inc(start, mid, idx * 2, left, right);
	interval_inc(mid + 1, end, idx * 2 + 1, left, right);
	tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
}

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	scanf("%s", str);
	for (int i = 0; i < n; i++) arr[i] = str[i] - '0';
	init(0, n - 1, 1);

	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		Node res = interval_sum(0, n - 1, 1, a - 1, b - 1);
		interval_inc(0, n - 1, 1, a - 1, b - 1);
		printf("%lld\n", res.sums);
	}

	return 0;
}