https://codeforces.com/problemset/problem/1661/D

저어어번 딥2인데 업솔빙 안한게 기억나서 품
water the tree 다음문제로 뒤에서부터 푸는 그리디인건
바로 눈치챘는데 나이브한 O(nk) 풀이에서
어떻게 O(n)로 줄일지 고민을 해야했음.

하나처리하고 앞으로갈때마다 이전에서 구한거에서 같은값을 계속 뺀다는게 핵심으로 이전연산으로 생긴 빼줄값 sum과 인덱스 하나 처리할 때마다 sum을 얼마나 줄일지를 나타내는 cnt 변수와 변수범위가 끝날때 몇개를 취소? 할지를 저장하는 배열하나만 있으면 되는 문제였음.

즉 뒤쪽인덱스를 대상으로 수행한 연산들의 배열값 변화량을 전부 합쳐서 생각하고 개수만 카운팅하는 개꿀잼 그리디 문제였음 *1900이여서 기분도 좋았음

범위를 업데이트하는 연산이라 펜윅이나 세그를 생각했는데
합과 카운팅문제로 바꾸는게 신박했음
이번 주 코포엔 이런 그리디 문제만 나왔으면 좋겠음
water the tree 같은 수학이나 이분탐색은 노잼임