[백준] 24915. 센터가 돋보여야 해

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

문제요약

• N개의 숫자(333,333, 숫자 33,333,333)
• Q개의 쿼리(333,333)
  • a < b < c 위치일때 ${A_b - A_a - A_c}$의 최대값
  • a의 위치를 c로 변경

접근법

• 세그먼트 트리를 사용해야할 것 같은데..
• 특정 구간에서 a < b 일때 ${A_b - A_a}$의 최대값은 구해볼 수 있겠음
  • 분할 정복
  • 구간 최대/최소/${A_b - A_a}$ 최대 모두 유지
  • 왼쪽, 오른쪽이 잘 구해졌다치고,
  • "오른쪽 최대 - 왼쪽 최소"와 비교해서 구간 ${A_b - A_a}$ 갱신
• 특정 구간에서 b < c일때 ${A_b - A_c}$의 최대값도 비슷하게 하면 되겠음
• ${A_b - A_a - A_c}$ 최대값은 어떻게??
• ${A_b - A_a}$와 ${A_c}$로 나누거나 ${A_b - A_c}$와 ${A_a}$로 나누어 생각해본다
• 한쪽은 최대, 한쪽은 최소이면 최대가 될 것임. 그리고 왼쪽의 최대는 유지하고 있고, 오른쪽의 최소도 유지하고 있음
• 분할정복을 이용해서 유지시켜나감
  • 왼쪽, 오른쪽이 잘 구해졌다고 치고
  • 왼쪽의 ${A_b - A_a}$ 최대 - 오른쪽의 ${A_c}$ 최소
  • 오른쪽의 ${A_b - A_c}$ 최대 - 왼쪽의 ${A_a}$ 최소
  • 그리고 이중에 최대값을 구간갱신
• 결과적으로 구간 정보에 5개가 들어감 : 최대, 최소, b-a최대, b-c최대, b-a-c최대
• 업데이트, 구간 정보 구할때 응용가능

주의점

• 경계값 처리를 잘해야함
  • 단순 최대/최소면 INF 값을 적절히 설정하면 됨
  • 빼기가 들어가면서 잘못 하면 INF - 최소 또는 최대 - (-INF)가 되면서 값이 꼬일 수 있기때문에 주의 필요
  • 구간 정보는 빼기의 방향을 고려해서 각각 저장해야함
• 쉽게 갈 줄 알았는데 어려웠음

테스트방법

• 제출 후 오류가 많이 발생해서 자체적인 테스트를 만듬
• k개 정도 랜덤 생성 후 모든 범위에 대해서 구현한 코드 동작
• 별도로 구현한 완전 탐색 코드와 값 비교 후 오류가 발생하는 테스트케이스 확인
• 값을 넣을때 경계값 : -333,333,333, 333,333,333 도 넣어서 추가 확인