[일반] 이런 문제 있음?

[캐티(tae826)]

어떤 수열에서 정해진 X에 대해서 연속된 X개의 합의 최댓값 구하기

세그로 lgN으로 구하고 싶고 수열에 갱신 있음

다른 문제 풀다가 부분 문제로 저 상황이 나왔고 풀이를 대충 알 것 같은데 저것만 따로 문제로 되어있는거 먼저 풀어보고 싶네

저런 거 있나? 금광이랑 비슷한데 금광은 정해진 X에 대한 게 아닌 것 같음

[익명(106.101)]

세그 노드마다 왼쪽에서 2^t개합 오른쪽 2^t개 합, 2^t개 합 최대 이런식으로 노드 n*lgn개 들고다니면서 호그제곱에 될거같은데 로그는 어케하는거지 - dc App

[캐티(tae826)]

i번째 원소에 ai가 있으면 i에 +ai, i+x에 -ai 넣고 1~K까지의 합을 구하면 그게 K-X ~ K 의 합인 것 같아서 그걸로 금광세그 비슷하게 하려고 했는데

[익명(223.62)]

저게 로그제곱에 됨?

[익명(223.62)]

결국에 연속한 X개 들어가는 모든 자리 다 구해보겠단거 아니야? 쿼리를 어케 sublinear로 한단건지 모르겠음

[익명(175.193)]

미리 연속된 x개 합들 주루룩 구해놓고 레이지세그?

[대학원오지마세요(publfl)]

X가 고정된값임 아니면 쿼리로 주어지는 값임?

[캐티(tae826)]

고정

[익명(106.101)]

아 고정이엇구나 - dc App

[대학원오지마세요(publfl)]

그러면 그냥 range change range max segtree로 됨

[캐티(tae826)]

레이지세그를 잘 못 짜서 못 떠올린듯.. 되게 쉬운거였네

[익명(112.187)]

금광으로 어떻게 안되나?

[chromate00(hjroh0315)]

https://www.acmicpc.net/problem/2559
업데이트 없는 버전은 여기 있습니다. 각 노드를 윈도우 하나로 보면 세그로 충분히 될 것 같고, 업데이트는 해당 위치가 들어가는 윈도우 (최대 2x-1개) 전체에 변화량만큼 더해주면 될 듯합니다

[캐티(tae826)]

걍 윈도우를 하나로 보고 레이지로 구간업뎃해도 되네.. 이렇게 쉬운방법이