[백준 1306번] [세그먼트 트리] 달려라 홍준

Approach

문제를 풀기 위해서 가장 중요한 것은 출제자의 의도를 읽는 것이다.

어느 범주에서 출제 했는지를 검토해보면, 이 문제는 주어진 쿼리의 최대값을 구하는 문제와 정확하게 동지이다.

 

추가적으로 범위라고 표현하기는 했지만, 궁극적으로 제시하고 싶은 정보는 쿼리의 길이이다.

슬라이딩 윈도우 기법을 활용해서 가능한 최저부터 최고까지 쭉 쓸고 가면 된다. 시간 복잡도는 $O(NlgN)$정도이므로, 뭐 충분하다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int seg[4000000];

int update(int node_index, int node_left, int node_right, int index, int value){
    if(index < node_left || node_right < index) return seg[node_index];

    if(node_left == node_right) return seg[node_index] = value;
    else{
        int mid = (node_left + node_right) / 2;
        return seg[node_index] = max(update(node_index * 2, node_left, mid, index, value), update(node_index * 2 + 1, mid + 1, node_right, index, value));
    }
}

int query(int node_index, int node_left, int node_right, int query_left, int query_right){
    if(query_right < node_left || node_right < query_left) return 0;
    if(query_left <= node_left && node_right <= query_right) return seg[node_index];
    else{
        int mid = (node_left + node_right) / 2;
        return max(query(node_index * 2, node_left, mid, query_left, query_right), query(node_index * 2 + 1, mid + 1 , node_right, query_left, query_right));
    }
}

// M : 쿼리 영역

int main(void){
    fastio;
    memset(seg, 0, sizeof(seg));

    int N, M;
    cin >> N >> M;

    for(int i = 1; i <= N; i++){
        int t;
        cin >> t;
        update(1, 1, N, i, t);
    }

    for(int i = M; i <= N - M + 1; i++){
        cout << query(1, 1, N, i - (M - 1), i + (M - 1)) << " ";
    }
    cout << "\n";

    return 0;
}