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

https://www.acmicpc.net/problem/17353

 

[필자 사고]

이 문제는 세그먼트 자료구조를 이용하는 거다.

다만 이 문제만의 특별한 점은 느린 세그먼트 자료구조를 이용하고

해당 lazy배열을 열이 2개 행이 4*N 형태로 설정하여 첫번째 열에는 시작점 두번째 열애는 공차를 저장하는 형태로

문제를 해결해야 된다.

 

[코드 해설]

1. SegmentTree 구조체

SegmentTree는 세그먼트 트리와 lazy propagation을 구현한 구조체로, 세그먼트 트리 초기화, 구간 업데이트, 점 단위 쿼리 등을 제공합니다.

주요 멤버 변수:

• segment_tree: 세그먼트 트리의 노드 값을 저장하는 벡터.
• lazy_updates: lazy propagation 처리를 위한 배열로, 구간 업데이트 정보를 저장합니다. 각 노드는 array<ll, 2> 형식의 값을 저장하며:
  • lazy_updates[node][0]: 구간에 더할 시작값.
  • lazy_updates[node][1]: 구간에 더할 값의 증가량.

---

2. initialize 함수

세그먼트 트리를 초기화하는 함수로, 다음을 수행합니다:

1. 트리 크기 설정:
   • 입력 크기 n을 기반으로, 트리의 크기를 2의 제곱 형태(tree_size)로 설정합니다.
2. 리프 노드 초기화:
   • 리프 노드(tree_size부터 시작)를 입력받은 값으로 초기화합니다.
3. 내부 노드 초기화:
   • 각 노드 값을 두 자식 노드 값의 합으로 계산합니다.

---

3. range_update 함수

구간 [left, right]를 업데이트하는 함수로, lazy propagation을 사용해 효율적으로 동작합니다.

• Lazy 적용:
  • 업데이트 전에 apply_lazy를 호출하여 현재 노드의 lazy 값을 반영합니다.
• 기저 사례:
  • 업데이트 구간이 현재 노드 범위와 겹치지 않으면 종료합니다.
  • 현재 노드 범위가 업데이트 범위에 완전히 포함되면 lazy 값을 설정하고 반영합니다.
• 재귀 호출:
  • 현재 노드를 좌우로 나누어 자식 노드에 대해 업데이트를 수행합니다.
• 값 갱신:
  • 자식 노드들의 값이 변경된 후, 부모 노드 값을 재계산합니다.

---

4. point_query 함수

특정 범위 [left, right]의 합을 계산하는 함수로, 점 단위 쿼리도 처리할 수 있습니다.

• Lazy 적용:
  • 질의 전에 apply_lazy를 호출하여 현재 노드의 lazy 값을 반영합니다.
• 기저 사례:
  • 쿼리 구간이 현재 노드 범위와 겹치지 않으면 0을 반환합니다.
  • 현재 노드 범위가 쿼리 범위에 완전히 포함되면 노드 값을 반환합니다.
• 재귀 호출:
  • 현재 노드를 좌우로 나누어 자식 노드에 대해 값을 계산한 후 합산합니다.

---

5. apply_lazy 함수

Lazy propagation을 적용하는 함수로, 다음을 수행합니다:

1. 자식 노드로 값 전파:
   • Lazy 값을 자식 노드에 전달하여 구간 업데이트를 연기합니다.
2. 현재 노드 값 갱신:
   • Lazy 값을 현재 노드 값에 반영합니다.
   • 노드 범위 길이와 lazy 증가량을 고려하여 값을 계산합니다.
3. Lazy 초기화:
   • 현재 노드의 lazy 값을 초기화합니다.

---

6. 메인 함수

프로그램의 시작점으로, 입력과 쿼리 처리를 담당합니다.

1. 입력 처리:
   • 요소 개수와 각 요소 값을 입력받아 세그먼트 트리를 초기화합니다.
2. 쿼리 처리:
   • 쿼리 개수만큼 반복하며, 다음 두 가지 작업을 수행합니다:
     • 구간 업데이트 (operation == 1): [start, end] 범위를 업데이트합니다.
     • 점 단위 질의 (operation == 2): start 위치의 값을 출력합니다.

[소스 코드]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int tree_size;
struct SegmentTree {
    vector<ll> segment_tree;
    vector<array<ll, 2>> lazy_updates;

    void initialize(int n) {
        for (tree_size = 1; tree_size < n; tree_size *= 2);
        segment_tree.assign(2 * tree_size, 0);
        lazy_updates.assign(2 * tree_size, { 0, 0 });

        for (int i = tree_size; i < tree_size + n; i++) {
            cin >> segment_tree[i];
        }
        for (int i = tree_size - 1; i >= 1; i--) {
            segment_tree[i] = segment_tree[2 * i] + segment_tree[2 * i + 1];
        }
    }

    void range_update(int left, int right, int node = 1, int node_left = 0, int node_right = tree_size - 1) {
        apply_lazy(node, node_left, node_right);

        if (node_right < left || right < node_left) return;
        if (left <= node_left && node_right <= right) {
            lazy_updates[node] = { node_left - left + 1, 1 };
            apply_lazy(node, node_left, node_right);
            return;
        }

        int mid = (node_left + node_right) / 2;
        range_update(left, right, 2 * node, node_left, mid);
        range_update(left, right, 2 * node + 1, mid + 1, node_right);
        segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
    }

    ll point_query(int left, int right, int node = 1, int node_left = 0, int node_right = tree_size - 1) {
        apply_lazy(node, node_left, node_right);

        if (node_right < left || right < node_left) return 0;
        if (left <= node_left && node_right <= right) return segment_tree[node];

        int mid = (node_left + node_right) / 2;
        return point_query(left, right, 2 * node, node_left, mid) +
            point_query(left, right, 2 * node + 1, mid + 1, node_right);
    }

    void apply_lazy(int node, int node_left, int node_right) {
        if (lazy_updates[node][1] != 0) {
            if (node < tree_size) {
                lazy_updates[2 * node][0] += lazy_updates[node][0];
                lazy_updates[2 * node][1] += lazy_updates[node][1];

                lazy_updates[2 * node + 1][0] += lazy_updates[node][0] + lazy_updates[node][1] * (node_right - node_left + 1) / 2;
                lazy_updates[2 * node + 1][1] += lazy_updates[node][1];
            }

            segment_tree[node] += lazy_updates[node][1] * (node_right - node_left) * (node_right - node_left + 1) / 2 +
                lazy_updates[node][0] * (node_right - node_left + 1);
            lazy_updates[node] = { 0, 0 };
        }
    }
} seg_tree;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int num_elements;
    cin >> num_elements;
    seg_tree.initialize(num_elements);

    int num_queries;
    cin >> num_queries;
    while (num_queries--) {
        int operation, start, end;
        cin >> operation >> start;

        if (operation == 1) {
            cin >> end;
            seg_tree.range_update(start - 1, end - 1);
        }
        else if (operation == 2) {
            cout << seg_tree.point_query(start - 1, start - 1) << '\n';
        }
    }

    return 0;
}