[일반] 이 문제 어캐 푸냐??

[익명(218.233)]

https://codeforces.com/contest/1709/problem/D

이거 세그트리 알아야 풀 수 있는 거임? 

O(nlogn+q)   

이게 어캐 나오지.. 쿼리마다 구간의 최댓값 구하는 방식으로 해볼려다가 딱 봐도 시간초과라 관뒀는데 세그트리 이용하면 빠르게 구할 수 있지 않음? 세그트리 안쓰고도 풀 수 있는 방법 있으면 알려줘

[캐티(tae826)]

구간의 최댓값 구하는거 맞는데 qlgn 아니고 q가 되나? 최댓값 구하는거 맞고 세그중에서도 간단한 류라 세그 쓰는게 맞아보이긴 함.. 안 쓰는 풀이는 잘 안 떠오른다

[익명(218.233)]

몰라서 막힐 때 배우려고 했는데 이제 배우면 되겠네 ㅋㅋ ㄳㄳ

[캐티(tae826)]

저 문제에서 구간의 최댓값 떠올린거 보면 세그 배워도 금방 잘 쓸 듯

[익명(218.233)]

[익명(110.11)]

구간의 값이 바뀌지 않으면서 최대/최소 구하는거는 전처리 o(nlogn) / 쿼리당 o(1)에 가능함

[익명(110.11)]

https://cp-algorithms.com/sequences/rmq.html
여기서
sparse table 참고
근데 나도 귀찮아서 세그 쓸 듯

[익명(218.233)]

일단 세그나 그런 특수한 알고리즘 모르는 상태면 풀기 힘든건 맞지?

[익명(110.11)]

ㅇㅇ 결국 구간의 최댓값을 빠르게 구해야하니까 저 링크에 있는 방법을 써야함

[익명(218.233)]