백준 17353 : 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

수열이 주어지고, Q개의 쿼리가 주어졌을 때 해당 쿼리를 처리하는 문제이다.

각 쿼리는 2개중 하나이며 처리해야하는 쿼리의 내용은 다음과 같다.

1. L ~ R범위에 1 ~ (R - L + 1)의 등타수열을 더한다.

2. X번째 값을 출력한다.

 

나는 이 문제를 레이지 프로퍼게이션을 이용하여 풀었다.

 

주어진 범위의 첫째항이 1이고 공차가 1인 등차수열을 더해가며, 규칙을 찾다보면 몇가지 규칙이 보이게된다.

범위에서 연산이 겹치는 경우 첫째항과 공차는 서로 더해진다.

예를 들어

1, 1, 1, 1, 1 와 같은 배열이 존재하고, 이 배열에 1번 쿼리2번을 다음과같이 처리했을 때

Q2 -> L = 1, R = 3

Q2 -> L = 2, R = 3

 

[2, 3]범위를 생각해보면

첫번째 쿼리를 처리했을때, 첫째항은 2, 공차는 1인 등차수열이

두번째 쿼리를 처리했을 때, 첫째항은 1, 공차는 1인 등차수열이 더해진다.

최종적으로, 첫째항은 3, 공차는 2인 등차수열이 더해지는것이다.

 

이 아이디어를 기반으로 레이지배열을 잡고, 레이지 프로퍼게이션을 돌리면 답을 구할 수 있다.

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;

ll n;
ll arr[100010];
ll tree[400010];
pair<ll, ll> lazy[400010]; //첫째항, 공차

void push(ll l, ll r, ll nd) {
    if (lazy[nd].first != 0 || lazy[nd].second != 0) {
        ll len = r - l + 1;
        tree[nd] += (len * (2 * lazy[nd].first + (len - 1) * lazy[nd].second)) / 2;
        if (l != r) {
            ll mid = (l + r) / 2;
            lazy[nd * 2].first += lazy[nd].first;
            lazy[nd * 2].second += lazy[nd].second;
            lazy[nd * 2 + 1].first += lazy[nd].first + (mid - l + 1) * lazy[nd].second;
            lazy[nd * 2 + 1].second += lazy[nd].second;
        }
        lazy[nd] = {0, 0};
    }
}

void init(ll st, ll ed, ll nd)
{
    if(st == ed) {
        tree[nd] = arr[st];
        return;
    }
    ll mid = (st + ed) / 2;
    init(st, mid, nd * 2);
    init(mid + 1, ed, nd * 2 + 1);
    tree[nd] = tree[nd * 2] + tree[nd * 2 + 1];
}

ll sum(ll st, ll ed, ll nd, ll l, ll r)
{
    push(st, ed, nd);
    if(ed < l || st > r) return 0;
    if(l <= st && ed <= r) return tree[nd];
    ll mid = (st + ed) / 2;
    return sum(st, mid, nd * 2, l, r) + sum(mid + 1, ed, nd * 2 + 1, l, r);
}

void Update_range(ll st, ll ed, ll nd, ll l, ll r) {
    push(st, ed, nd);
    if (ed < l || st > r) return;
    if (l <= st && ed <= r) {
        lazy[nd].first += 1 + (st - l);
        lazy[nd].second += 1;
        push(st, ed, nd);
        return;
    }
    ll mid = (st + ed) / 2;
    Update_range(st, mid, nd * 2, l, r);
    Update_range(mid + 1, ed, nd * 2 + 1, l, r);
    tree[nd] = tree[nd * 2] + tree[nd * 2 + 1];
}


int main()
{
    ll i, j;
    scanf("%lld", &n);
    for(i=1;i<=n;i++) scanf("%lld", &arr[i]);
    init(1, n, 1);
    int Q;
    scanf("%d", &Q);
    while(Q--) {
        int type;
        scanf("%d", &type);
        if(type == 1) {
            ll L, R;
            scanf("%lld %lld", &L, &R);
            Update_range(1, n, 1, L, R);
        }
        else {
            ll x;
            scanf("%lld", &x);
            printf("%lld\n", sum(1, n, 1, x, x));
        }
    }
    return 0;
}