세그멘트트리 많이 보는 유형 3문제

유형이 비슷하고, 자주 나오는 것 같아서 같은 곳에 풀이를 적습니다.

이 유형의 문제들에서는, 보통 2개 (혹은 그 이상)의 축이 나오고, 대소관계를 비교하는 쿼리를 해결해야합니다.

 

한 축을 정렬하여 한쪽의 대소관계를 강제한 뒤, 다른 축을 순차적으로 업데이트 해 쿼리를 해결할 수 있습니다.

 

 

 

1. 북서풍

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

5419번: 북서풍

이 유형의 가장 간단한 버젼입니다. 

문제를 간단히 요약하면, 2차원 평면에 섬들이 놓여있습니다.

여기서 우리는 각 섬에서 북서쪽에 있는 섬들의 갯수 합을 구하면 됩니다.

 

섬을 $x$축순으로 정렬한다면, 기존의 섬들은 현재 보고 있는 섬보다 모두 $x$좌표가 같거나 낮을 것입니다. 이것으로 조건 중 하나인 서쪽을 빼버릴 수 있어서, 차례로 업데이트 하며 자신보다 북쪽에 있는 섬들만 세주면 됩니다.

 

주의할 점은,  같은 $x$축 좌표를 가진다면 $y$좌표가 큰 섬이 먼저 정렬되도록 해야합니다. (그래야 아래 섬에서 윗 섬을 셀 수 있습니다.)

 

2. 카드 공장(Large)

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

재미있는 관찰이 필요한 문제입니다.

 

카드 앞면이 $a$, 뒷면이 $b$로 이루어진 카드 ($a \leq b$)가 있다고 가정합시다.

만약 명령 $q$가 들어온다면, 다음 세가지 경우 중 하나입니다.

1) $q \lt a$

카드에 아무런 변화가 일어나지 않습니다.

2) $a\leq q<b$

카드가 무조건 $b$가 됩니다. (큰 값)

3) $b\leq q$

카드가 뒤집힙니다.

 

중간 2)번 쿼리는 이전 상황과 관계 없이, 무조건 카드를 $b$로 바꿉니다.

고로 우리는 각 카드마다 가장 마지막으로 행해지는 2번쿼리를 찾은 뒤, 그 이후 3번 쿼리의 홀짝성에 따라 카드가 결정됨을 알 수 있습니다. 

 

우선 각 카드마다 마지막으로 행해지는 2번 쿼리를 찾는 방법입니다. 

구간 최대 세그트리를 이용하는데, 나오는 카드 앞면 뒷면 값, 쿼리의 값들을 모두 좌표압축 시킨 뒤 각 앞, 뒷면 사이에 있는 쿼리 인덱스의 최댓값을 구하면 됩니다. 

 

이제 각 카드마다 마지막 2번 쿼리의 인덱스를 구했으니, 각 2번 쿼리 뒤에 나오는 3번 쿼리의 갯수를 구할 차례입니다.

이는 우리가 구한 인덱스를 역정렬한 뒤, 뒤에서부터 원소를 하나씩 갱신해 나가면서 조건에 맞는 3번 쿼리의 갯수를 sum 세그멘트 트리를 이용해 계산해 주면 됩니다.  

 

3. 시험

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

17668번: 시험

하나의 쿼리는 위 그림처럼 나타낼 수 있습니다.

빗금친 구간의 학생 수를 구하는 것이 우리의 목표입니다.

하지만 제한하는 축이 3개이기 때문에, 기존의 방법으로는 할 수 없습니다.

같은 그림을 다르게 보면, 위 그림에서 빨간 빗금 구역과, 검은 빗금 구역은 축이 2개씩 있는 것을 알 수 있습니다. 

빨간 빗금은 $x+y$ 순으로 역정렬한 뒤 파란 선보다 $y$값 큰 좌표들 구하기

검은 빗금은 $x+y$ 순으로 역정렬한 뒤 빨간 선보다 $x$값 작은 좌표들 구하기

로 구할 수 있습니다.

우리가 원하는 답은 빨 - 검입니다.

 

예외적으로 다음처럼 a+b>c이면 y=-x+c 선은 고려할 필요가 없게 됩니다.

고로 위 1번 문제인 북서풍 처럼 풀면 됩니다.