쌓기나무

시간 제한2초메모리 제한1024 MB

요약
칸마다 블록을 쌓거나 제거하는 질의가 주어질 때, 정면, 측면, 윗면에서 보이는 블록의 개수를 각각 구한다.
난이도

보통10점 중 6점

유형
구현, 해시맵, 시뮬레이션
정답자
아직 제출이 없습니다

문제

PIMM 알고리즘 스터디에서 멘토로 활동하는 민규는, 알고리즘 수업 자료로써 격자판 형태의 칸에 ”쌓기나무”를 쌓고 있다.

민규는 격자판의 형태를 가로축이 X\text{X}축이고 세로축이 Y\text{Y}축이며, 00 또는 양의 정수 좌표만 존재하는 2차원 좌표평면 형태로 정했다. 격자판의 각 칸은 2차원 좌표쌍 (i,j)(i, j) 형식으로 구분된다. 민규는 격자판의 빈칸에 새로운 블록을 쌓거나, 쌓인 블록의 가장 위에 새로운 블록을 쌓거나, 이미 쌓인 블록을 제거할 수 있다. 이때 모든 블록이 붙어있어야 할 필요는 없다.

격자판에 쌓인 쌓기나무를 바라보면 어떤 블록은 다른 블록에 가려져 보이지 않는다. 아래 그림과 같이 Z\text{Z}축을 도입한 3차원 좌표계에서 쌓기나무의 한 면이 XZ\text{XZ} 평면과 평행이 되게 바라볼 때를 ”쌓기나무를 정면에서 바라보고 있다”고 하며, YZ\text{YZ} 평면과 평행이 되게 바라볼 때를 ”쌓기나무를 측면에서 바라보고 있다”고 한다. 또, XY\text{XY} 평면과 평행이 되게 바라볼 때를 ”쌓기나무를 윗면에서 바라보고 있다”고 한다.

영도는 민규의 수업 준비를 위해 쌓기나무를 직접 프로그램으로 구현하려 한다. 영도를 도와 아래 쿼리들을 수행하는 프로그램을 작성하시오.

  • STACK i j: XY\text{XY} 평면 상의 (i,j)(i, j) 칸에 나무 블록을 한 개 쌓는다.
  • REMOVE i j: XY\text{XY} 평면 상의 (i,j)(i, j) 칸의 가장 위에 위치한 나무 블록 한 개를 제거한다. 제거할 나무 블록이 없다면, 이 쿼리를 무시한다.
  • FRONT: 쌓기나무를 정면에서 봤을 때 보이는 나무 블록의 개수를 출력한다.
  • SIDE: 쌓기나무를 측면에서 봤을 때 보이는 나무 블록의 개수를 출력한다.
  • TOP: 쌓기나무를 윗면에서 봤을 때 보이는 나무 블록의 개수를 출력한다.

입력

첫 번째 줄에 좌표평면 상에서 블록을 쌓을 수 있는 X\text{X} 좌표 범위 NN, Y\text{Y} 좌표 범위 MM, 쿼리의 개수 QQ가 공백으로 구분되어 주어진다.

두 번째 줄부터 QQ개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

출력

첫 번째 줄부터 FRONT, SIDE, TOP 쿼리가 주어질 때마다 정답을 결과를 한 줄에 하나씩 순서대로 출력한다.

제한

  • 1≤N,M≤200,0001 \le N, M \le 200\\,000
  • 1≤Q≤500,0001 \le Q \le 500\\,000
  • 0≤i\<N0 \le i\<N
  • 0≤j\<M0 \le j\<M
  • FRONT, SIDE, TOP 중 하나의 쿼리가 입력으로 한 줄 이상 주어짐이 보장된다.

예제2

  1. 예제 1

    입력
    2 2 7
STACK 1 0
STACK 0 1
STACK 1 1
STACK 1 1
FRONT
SIDE
TOP
    예상 출력
    3
3
3

  2. 예제 2

    입력
    3 2 6
STACK 0 0
TOP
STACK 2 0
FRONT
REMOVE 0 0
SIDE
    예상 출력
    1
2
1