2094. 강수량

오랜만에 어려운 거 풀어서 기분이 좋다.

2094번: 강수량

---

문제를 잘 읽고 이 글을 보길 바란다.

 

정수 $X$와 $Y$가 주어질 때, 다음의 세 가지 조건이 모두 참이어야 주어진 질문에 ``참``이라고 할 수 있다.

1. 구간 $[Y, X]$에 속한 모든 연도의 강수량이 알려져 있어야 한다.
2. $X$년도의 강수량이 $Y$년도의 강수량 이하여야 한다.
3. 구간 $(Y, X)$에 속한 모든 연수의 강수량이 $X$년도의 강수량보다 적어야 한다.

위의 세 조건 중 하나라도 만족하지 못하면 주어진 질문에 ``거짓``이라고 답해야 한다.

 

그러나, 참이라고도 거짓이라고도 대답할 수 없는 경우가 있다. 예를 들어 $Y$년도와 $X$년도 사이에 속한 일부 연도의 강수량이 알려지지 않았다던가, $Y$년도 또는 $X$년도의 강수량이 알려지지 않았을 경우가 있다. 이런 경우에는 ``알 수 없음``이라고 대답해야 한다. 

 

편의상 ``참``은 0, ``알 수 없음``은 1, ``거짓``은 2라고 하겠다. 이제 주어진 쿼리에 답해보자.

 

우선 $Y$년도와 $X$년도의 강수량이 모두 주어진 경우를 생각해 보자. 조건 2나 조건 3 중 하나라도 만족하지 못하면 정답은 2이다. 조건 2와 조건 3을 둘 다 만족하더라도 조건 1을 만족하지 못하면 정답은 1이고, 조건 1, 2, 3을 모두 만족할 때에만 정답이 0이라고 확신할 수 있다.

 

이제 $Y$년도의 강수량만 주어진 경우를 생각해 보자. $X$년도의 강수량이 주어지지 않았지만, $X$보다 빠른 연도 중 강수량이 주어진 제일 늦은 연도를 $R$년이라고 하면 구간 $(Y, R]$의 강수량의 최댓값 $max$와 $Y$년의 강수량을 비교해볼 수 있다. $max<rain(Y)$이라면 정답은 1이고, 그렇지 않다면 2이다.

 

같은 방법으로 $X$년도의 강수량만 주어졌을 때도, $Y$년보다 늦으면서 강수량이 주어진 가장 빠른 연도를 $L$년이라고 할 때 구간 $[R,X)$의 강수량의 최댓값 $max$과 $rain(X)$를 비교해볼 수 있다. 마찬가지로 $max<rain(X)$라면 정답은 1, 그렇지 않다면 2이다.

 

마지막으로 $Y$년과 $X$년의 강수량이 둘 다 주어지지 않은 경우가 있다. 이 경우에는 정답을 1로 확정할 수밖에 없다.

 

구간의 최댓값을 구하는 과정은 세그먼트 트리로 쉽게 처리할 수 있고, $X$년보다 빠른 연도 중 강수량이 주어진 가장 늦은 연도는 이분 탐색으로 구할 수 있다. 코딩 실수만 하면 무난하게 해결할 수 있다.

---

솔직히 플3까지는 아닌 거 같은데..?