[백준 17353번] [Lazy propagation] 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

Approach

구간에 대한 정보를 업데이트를 하는 상황이므로 Lazy propagation임은 쉽게 파악할 수 있었을 것이다.

문제 출제 범위에 대해서는 쉽게 파악이 가능하지만, 가장 껄끄러운 지점은 구간에 대한 정보가 업데이트 될 때 각 위치 별로 업데이트 되는 양이 다르다는 것이다. 즉 이러한 문제점으로 인해 세그먼트 트리의 update과정에서 공통된 연산을 정의할 수 없게 된다.

 

즉. 이 문제를 Lazy propagation으로 풀기 위해서는

이 문제에서 각 위치 별로 업데이트 되는 양이 달라서 발생하는 문제점을 해결해주면 된다.

 

잘 생각해보면 업데이트 되는 정도가 1씩 증가하는 양상을 볼 수 있다. 즉 차이가 일정하다.

"차이가 일정하다는 것을 활용해서 업데이트 되는 것을 정의할 수 없을까"라는 질문에 조금만 귀를 귀울여 보면, "차이를 새로운 변수"로 잡으면 쉽게 해결할 수 있다는 것을 알 수 있다.

 

예를 들어 $a_i$ - $a_{i - 1}$ = $b_i$라 하자. $a_2$를 1 증가시킨다는 것의 의미는 $a_1$과의 차이를 1 증가시킨다는 것과 동치이므로 $b_i$의 값을 1 키우면 된다.

 

해당 사실을 이용하여 Lazy propagation을 진행해주면 된다.

 

단, 특정한 점을 증가시켰을 때 위의 방향과의 차이도 보정해주어야 한다는 점을 명심해야 한다.

위의 예시처럼 $a_2$를 1 증가시켰을 때 $b_2$만 1 증가시키는 것이 아니라, $b_3$도 -1시켜야한다는 것을 주의해야 한다. (차이가 좁아지는 것이므로)

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};
ll seg[400004];
ll lazy[400004];

void propagate(int node, int left, int right){
    if(lazy[node]){
        if(left != right){
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        seg[node] += lazy[node] * (right - left + 1);
        lazy[node] = 0;
    }
}

void update(int node, int start, int end, int left, int right, int value){
    propagate(node, start, end);
    if(right < start || end < left) return;
    if(left <= start && end <= right){
        lazy[node] += value;
        propagate(node, start, end);
        return;
    }
    int mid = (start + end) >> 1;
    update(node * 2, start, mid, left, right, value);
    update(node * 2 + 1, mid + 1, end, left, right, value);
    seg[node] = seg[node * 2] + seg[node * 2 + 1];
}

ll query(int node, int start, int end, int left, int right){
    propagate(node, start, end);
    if(right < start || end < left) return 0;
    if(left <= start && end <= right) return seg[node];
    int mid = (start + end) >> 1;
    return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right); 
}

int main() {
    fastio;
    int n;
    cin >> n;
    int tmp = 0;
    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        update(1, 1, 100000, i, i, t - tmp);
        tmp = t;
    }

    int m;
    cin >> m;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a;
        if(a == 1){
            cin >> b >> c;
            update(1, 1, 100000, b, c, 1);
            update(1, 1, 100000, c + 1, c + 1, - (c - b + 1));
        }
        else{
            cin >> b;
            cout << query(1, 1, 100000, 1, b) << "\n";
        }
    }
    return 0;    
}