BOJ 1306, 달려라 홍준
ProblemSolving ·이 문제는 세그먼트 트리를 이용한 문제입니다.
풀이
업데이트는 할 필요는 없습니다. 세그먼트 트리를 리프노드 중 큰 값으로 바텀업 방식으로 초기화 해주었습니다.
그 후 쿼리에서 값만 출력해오면 되는 문제입니다.
근데 홍준이가 이상한 놈이라 쿼리의 범위를 구하는 걸 조금 신경쓰셔야 합니다.
m번째 부터 n-m+1까지만 가고 앞뒤로 m을 보겠답니다. 참 골치 이상한 놈입니다. m씩 보겠다고해서 2m+1을 보는 것도 아닙니다.
아마 현재 자기 위치를 포함해서 앞으로 m만큼 뒤로 m만큼 보겠다는 것 같습니다. 총 2m-1만큼 보겠답니다.
query(i-m+1,i+m-1)를 돌려준다면 결과를 구할 수 있습니다!
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
using namespace std;
int h, n, m, Max;
vector<int> tree;
int arr[1000002];
void query(int left, int right)
{
left += h;
right += h;
Max = 0;
for (; left < right; left /= 2, right /= 2)
{
if (left % 2)
Max = max(Max, tree[left++]);
if (!(right % 2))
Max = max(Max, tree[right--]);
}
if (left == right)
Max = max(Max, tree[left]);
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
h = (1 << (int)log2(n - 1) + 1);
tree.resize(h * 2 + 1, 0);
for (int i = h; i < h + n; i++)
tree[i] = arr[i - h];
for (int i = h - 1; i > 0; i--)
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
for (int i = m - 1; i <= n - m; i++)
{
query(i - m + 1, i + m - 1);
printf("%d ", Max);
}
return 0;
}