티스토리 뷰

알고리즘 관련/BOJ

BOJ)3002 아날로그 다이얼

JASON 자손9319 2017. 1. 11. 17:04

문제: 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)숫자를 더해줘서 출력해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <algorithm>
#define MAX_N 250000
using namespace std;
int seg[* MAX_N][10], lazy[* 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 * + 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 * + 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&&<= 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 * + 1, mid + 1, y);
    for (int i = 0; i < 10; i++)
        seg[node][i] = seg[node * 2][i] + seg[node * + 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&&<= 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 * + 1, mid + 1, y);
}
int main() {
    scanf("%d%d"&n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%1d"&x);
        init(i, x, 11, n);
    }
    while (m--) {
        scanf("%d%d"&x, &y);
        printf("%d\n", query(x, y, 11, n));
        update(x, y, 11, n);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)11505 구간 곱 구하기  (2) 2017.01.12
BOJ)5012 불만 정렬  (2) 2017.01.11
BOJ)3002 아날로그 다이얼  (0) 2017.01.11
BOJ)1168 조세퍼스 문제2  (0) 2017.01.11
BOJ)9426 중앙값 측정  (7) 2017.01.11
BOJ)5676 음주 코딩  (0) 2017.01.10
댓글
댓글쓰기 폼