BOJ)3002 아날로그 다이얼

문제: icpc.me/3002

N개의 다이얼이 주어졌을 때 구간이 주어지면 구간의 합을 구한뒤 구간의 수를 전부 1씩 증가시켜주는 문제이다.

얼핏보면 구간에 대한 증가연산과 구간합을 출력하면 되니 레이지 프라퍼게이션을 이용한 구간합으로 바로 해결할 수 있을것 같지만 문제는 다이얼이기 때문에 9를 증가시키면 0이 된다는 것이다.

결국 0~8의 숫자는 증가시킬 경우 1씩증가하게 되지만 9는 증가시킬 경우 오히려 -9가 되버린다. 이래서 구간에 대한 합을 한번에 노드에 저장하고 있을 경우 증가연산이 애매해질 우려가 있다.

따라서 우리는 구간마다 노드를 10개씩 만들어 0~9까지의 개수를 저장하여 값을 증가시키는 경우 0~9 ->(0+x)%10~(9+x)%10까지로 쉬프트 시킬것이다.

물론 구간에 대한 증가가 이루어지기 때문에 레이지 프라퍼게이션을 사용해야 한다.

결국 우리는 노드마다 0~9까지의 개수를 각각 저장하고 쿼리를 계산할 때 (0~9)숫자의 개수*(0~9)숫자를 더해줘서 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#define MAX_N 250000
using namespace std;
int seg[4 * MAX_N][10], lazy[4 * MAX_N], n, m, x, y, v[10];
void u_lazy(int node, int x, int y) {
    if (!lazy[node])return;
    for (int i = 0; i < 10; i++) 
        v[(i + lazy[node]) % 10] = seg[node][i];
    for (int i = 0; i < 10; i++)
        seg[node][i] = v[i];
    if (x != y) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
    return;
}
int init(int pos,int val ,int node, int x, int y) {
    if (pos < x || y < pos)
        return seg[node][val];
    if (x == y)
        return seg[node][val] = seg[node][val] + 1;
    int mid = (x + y) >> 1;
    return seg[node][val] = init(pos, val, node * 2, x, mid) + init(pos, val, node * 2 + 1, mid + 1, y);
}
void update(int lo, int hi, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)
        return;
    if (lo <= x&&y <= hi) {
        lazy[node]++;
        u_lazy(node, x, y);
        return;
    }
    int mid = (x + y) >> 1;
    update(lo, hi, node * 2, x, mid);
    update(lo, hi, node * 2 + 1, mid + 1, y);
    for (int i = 0; i < 10; i++)
        seg[node][i] = seg[node * 2][i] + seg[node * 2 + 1][i];
}
int query(int lo, int hi, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi) {
        int ret = 0;
        for (int i = 1; i < 10; i++) {
            ret += seg[node][i] * i;
        }
        return ret;
    }
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%1d", &x);
        init(i, x, 1, 1, n);
    }
    while (m--) {
        scanf("%d%d", &x, &y);
        printf("%d\n", query(x, y, 1, 1, n));
        update(x, y, 1, 1, n);
    }
    return 0;
}