BOJ 17668

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

 

코드

http://boj.kr/c12e64a1abaf44e6962f0cbae0872a06

 

JOI 2018/2019 Spring Training Camp 1-1

 

난이도 : D5

 

Elapse Time : 65min

 

값의 업데이트가 없어 오프라인 쿼리로 처리 가능하다는 것이 눈에 먼저 들어왔다. 가장 먼저 한 생각은 기준 3가지 중 정렬을 통해 1가지를 줄이는 것이었다. 학생들의 시험 점수쌍을 $S_i+T_i$를 기준으로 정렬하고 마찬가지로 쿼리도 $Z_j$를 기준으로 정렬하면 각 쿼리에서 점수 합 기준을 만족하는 점수 쌍들만 가지고 판단할 수 있다. 여기까지는 그냥 #2336과 비슷한 문제라고만 생각했지만 #2336에서는 다른 두 기준을 가지고 성립요건을 만족하는지만 판단하면 됐지만 이 문제에서는 성립요건을 만족하는 사람의 수를 세야 한다는 차이점이 있었다. 현재 가지고 있는 시험 점수 쌍 중 $S_i\geq X_j$, $T_i\geq Y_j$를 만족하는 쌍의 수를 구해야 하는데 좌표압축을 해놓고 머지소트 트리를 활용하면 어떨까 싶었지만 쿼리를 처리함에 따라 시험 점수 쌍이 늘어나는데 이때마다 업데이트를 해주어야 하므로 포기했다. 다른 방법을 찾으려고 좌표 평면에 $S\geq X$, $T\geq Y$, $S+T\geq Z$의 그림을 그렸는데 $X+Y$와 $Z$의 대소관계에 따라 영역의 모양이 달라지는 것을 확인했다. $X+Y\geq Z$라면 앞의 두 조건만 만족해도 세 번째 조건이 만족되므로 두 조건을 만족하는 쌍의 수만 구해주면 되고 $X+Y<Z$라면 $S_i+T_i\geq Z$를 만족하는 $i$ 중 $S_i<X$, $T_i<Y$ 중 하나를 만족하는 쌍의 수를 빼주면 된다는 것을 확인했다. 기준에 따라 쿼리를 두 종류로 나눈 뒤 각각의 쿼리를 기준에 따라 정렬하고 값 압축과 펜윅트리를 활용하여 답을 구했다.