본문 바로가기

알고리즘 관련/BOJ

BOJ)10999 구간 합 구하기2

문제: icpc.me/10999


구간에 대한 합을 출력하는 문제이다. 그런데 쿼리중에 구간에 대한 갱신 연산을 하는 쿼리가 있다.


우리는 세그먼트 트리를 통해 구간에 대한 갱신과 합쿼리를 빠르게 처리 할 수 있지만 구간에 대한 갱신을 세그먼트 트리로만 하려고 한다면 갱신의 경우 최악의 시간복잡도는 O(NlogN)이 될것이다. 


만약 쿼리가 전부 갱신만 들어온다면 시간 복잡도는 O(N(M+K)logN)로 당연히 시간초과를 보게 될 것이다.


그래서 우리는 lazy propagation을 이용하여 구간에 대한 갱신을 조금 더 빠르게 해주는 테크닉을 이용하여 문제를 풀어야만 한다.


lazy propagation에 대한 설명은 여기에 친절하게 되어있다.


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
#include <cstdio>
#include <algorithm>
#define MAX_N 1000000
typedef long long ll;
using namespace std;
ll n, m, k, seg[* MAX_N], lazy[* MAX_N], a, b, c, d;
void update_lazy(ll node, ll x, ll y) {
    if (!lazy[node])
        return;
    seg[node] += (y - x + 1)*lazy[node];
    if (x != y) {
        lazy[node * 2+= lazy[node];
        lazy[node * + 1+= lazy[node];
    }
    lazy[node] = 0;
}
ll update(ll lo, ll hi, ll val, ll node, ll x, ll y) {
    update_lazy(node, x, y);
    if (y < lo || hi < x)
        return seg[node];
    if (lo <= x&&<= hi) {
        lazy[node] += val;
        update_lazy(node, x, y);
        return seg[node];
    }
    ll mid = (x + y) >> 1;
    return seg[node] = update(lo, hi, val, node * 2, x, mid) + update(lo, hi, val, node * + 1, mid + 1, y);
}
ll query(ll lo, ll hi, ll node, ll x, ll y) {
    update_lazy(node, x, y);
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&<= hi)
        return seg[node];
    ll mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * + 1, mid + 1, y);
}
int main() {
    scanf("%lld%lld%lld"&n, &m, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld"&a);
        update(i, i, a, 11, n);
    }
    for (int i = 0; i < m + k; i++) {
        scanf("%lld"&a);
        if (a == 1) {
            scanf("%lld%lld%lld"&b, &c, &d);
            update(b, c, d, 11, n);
        }
        else {
            scanf("%lld%lld"&b, &c);
            printf("%lld\n", query(b, c, 11, n));
        }
    }
    return 0;
}
cs


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

BOJ)2336 굉장한 학생  (0) 2017.01.13
BOJ)1395 스위치  (0) 2017.01.13
BOJ)11505 구간 곱 구하기  (2) 2017.01.12
BOJ)5012 불만 정렬  (2) 2017.01.11
BOJ)3002 아날로그 다이얼  (0) 2017.01.11