최고의 친구

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

요약
기지국을 추가하거나 제거하면서, 두 친구 (x,0)과 (-x,0)와 예각삼각형을 이루는 기지국의 수를 각 질의마다 센다.
난이도

어려움10점 중 8점

유형
기하, 동적 계획법, 세그먼트 트리, 조합론
정답자
아직 제출이 없습니다

문제

범수와 윤성이는 둘도 없는 최고의 친구이다. 두 친구가 살고 있는 마을은 22차원 좌표평면으로 표현된다. 둘은 같은 마을에 살고 있지만 범수는 xx축의 양의 방향, 윤성이는 xx축의 음의 방향에 살고 있어 서로 만날 수 없다. 따라서 두 친구는 주로 게임을 하며 우정을 다진다.

게임을 위한 통신은 좌표평면 위의 기지국에서 이루어진다. 원활한 게임을 위해서는 통신 속도가 충분히 빨라야 한다. 범수의 위치, 윤성이의 위치, 기지국의 위치가 예각삼각형을 이룰 때에만 초고속 통신을 이용해 게임을 즐길 수 있다. 아쉽게도 마을은 하루가 다르게 개발되고 있어서 둘의 위치와 기지국의 정보가 시시각각 변한다. 따라서 당신은 다음과 같은 QQ개의 질의를 처리해야 한다.

  • 1 xx: 범수의 위치가 (x,0)(x,0), 윤성이의 위치가 (−x,0)(-x,0)일 때 초고속 통신이 가능한 기지국의 개수를 출력한다.
  • 2 xx yy: (x,y)(x,y)에 기지국이 없었다면 새로 설치하고, 있었다면 철거한다. 기지국의 위치는 xx축 위에 있지 않다.

초기에는 아무 기지국도 설치되어 있지 않다. 두 친구의 우정을 위해 질의를 올바르게 처리하는 프로그램을 작성하여라.

입력

첫 번째 줄에 질의의 개수 QQ가 주어진다. (1≤Q≤300,000)(1\le Q \le 300\\,000)

두 번째 줄부터 QQ개의 줄에 걸쳐 질의가 아래와 같은 형식 중 하나로 주어진다.

  • 1 xx: (1≤x≤109)(1 \le x \le 10^9)
  • 2 xx yy: (−109≤x,y≤109;y≠0)(-10^9 \le x,y \le 10^9; y \ne 0)

주어지는 수는 모두 정수이며, 11번 질의가 11번 이상 주어짐이 보장된다.

출력

각 11번 쿼리에 대한 답을 차례대로 각 줄에 걸쳐 출력한다.

예제1

  1. 예제 1

    입력
    7
    2 0 1
    2 0 2
    2 0 3
    1 2
    1 1
    2 0 3
    1 1
    
    예상 출력
    1
    2
    1