[백준] 33543. 둘이 한 팀

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

문제요약

• (A,B) 쌍이 N개 있음 (N : 25만, AB : 100만)
• query가 주어짐. A를 일괄 증가시키거나, B를 일괄 증가(Q : 25만)
• query가 주어질때마다 max(A,B)의 합을 구하는 문제

접근법

• query마다 A(또는 B)를 일괄 증가시키고 max(A,B)를 구하는 것은 시간 초과
• A > B의 관계는 언제 바뀔까? (또는 B < A)
  • A가 B에 비해 엄청 크면, 어지간한 B의 일괄증가에도 A>B 관계는 유지됨
  • A가 B에 비해 애매하게 크면, B의 일괄 증가에 A>B가 B<A가 될 수 있음
  • A, B 중에서 누가 선택되는지만 알 수 있다면 좋겠다!!!
• (A-B)로 오름차순 정렬을 함
• 0이 되는 시점 이전에는 A<B => B가 선택
• 0이 되는 시점부터는 A>B => A가 선택
• 이때 기준점 0이 일괄 증가에 따라 바뀜 => b-a
  • B를 일괄 증가시켰다면(+b만큼) 0이 기준점이 아니라 +b가 기준점이 됨
    • A-B로 정렬을 했기때문에 +b만큼 일괄 반영을 해야하기때문에
    • 예를 들어 A:10, B:3, A-B=7인 상황에서, B가 +7 일괄증가하면 A-B는 0이 됨
  • 같은 논리로 A를 일괄 증가시켰다면(+a만큼) 기준점에서 -a를 해줘야함
• 기준점을 찾았다면, k라고 하고
  • 0~k-1까지는 B를 선택 + B의 누적 증가분
  • k~n-1까지는 A를 선택 + A의 누적 증가분
  • 부분합은 누적합을 이용해서 계산