[백준] 22959. 신촌 수열과 쿼리

https://www.acmicpc.net/problem/22959

요약

• 수열이 주어지고 쿼리를 수행
• 특정 위치 업데이트 쿼리
• i 를 포함하는(l ~ ... i ... ~ r) 값이 j이상인 구간합의 최대값 쿼리

접근법

• 두번째 쿼리에서 구간합이 최대이려면 j 이상인 가장 긴 l과 r을 찾아야함
• 특정 i 위치를 기준으로 왼쪽으로 j보다 큰 것을 찾고, 오른쪽으로 j보다 큰 것을 찾고.....는 시간초과
• 이분탐색으로 특정 구간에서 최소값이 j보다 크면? 구간의 길이를 늘려볼만 함
• 최소값이 j보다 작으면? 구간을 줄여봐야함
• 구간트리 사용
  • 최소값 구간트리
  • 합 구간 트리
• i를 기준으로 [l, i]의 최소값이 j인 가장 먼 l을 찾음
• r도 마찬가지로 찾음
• 시간 복잡도 = 쿼리 (합구간트리 + 이분탐색 구간트리) = ${O(M * (logN + logN * logN)) = O(MlogNlogN)}$

주의점

• 시간이 빡빡해서 bottom-up으로 해야한다고 함