[일반] 구간 lazy 쿼리를 하는 상황 속에서 최대 누적합 구하기

[익명(112.186)]

근데 그 누적합이 원소 처음부터 더하는 값이어야 함

예를 들어 [1, x], [1, y]와 같은 구간의 누적합이 필요함

이거 절실히 필요한데 짜는법 아는 사람 있음?

[익명(49.170)]

그냥 세그 아님?

[익명(112.186)]

내가 빡통이라 그런지 그 세그 구현을 못 찾겠음 구간 [l, r]에서 최대 누적합. 그런데 그 형태는 반드시 처음부터 끝점까지 더한 값

[익명(110.76)]

S[i]에 대한 누적합을 구할거임
l부터 r까지 k를 더한다고 하자
1부터 i까지의 합을 S[i]라고 하면
l<=i<=r이면 S[i]는 (i-l+1)*k만큼 늘어나고
i>=r이면 S[i]는 (r-l+1)*k만큼 늘어남
이거는 a*i+b를 구간에 합하는 쿼리를 처리하는 세그먼트 트리를 만들면 해결할 수 있음
https://www.acmicpc.net/problem/17353
이거 풀어보면 도움 될 듯

[익명(110.76)]

S[i] 말고 A[i]에 대한 누적합

[익명(112.186)]

ㄳ