문제
레드의 성공을 보고, 지우는 그의 발자취를 따라가고자 한다. 그래서 그는 최대한 많은 포켓몬을 잡고자 한다. 그러나, 그가 가는 길에 다른 많은 포켓몬 트레이너들이 있기 때문에 그들을 쓰러뜨리려 한다.
레드와 지우는
각 지역마다 포켓몬 트레이너들이 있다. 그 곳을 통과하기 위해서는 포켓몬 트레이너와 전투를 해야 한다. 각 포켓몬 트레이너는 다른 트레이너에 대해 상대적인 레벨을 갖고 있다. 우리는 모든 포켓몬 트레이너들이 서로 다른 레벨을 갖고 있다고 가정한다. (즉, 모든 전투에서 명확한 승자가 있다는 것을 보장한다.)
세계는 끊임없이 변화하기 때문에 포켓몬 트레이너는 승리 확률을 높이기 위해 때때로 포켓몬의 타입을 바꾼다. 이 때문에 지우는 원정을 시작하기 가장 좋은 시기를 계획하고 싶어한다. 지우는 특정 지역에서 원정을 시작하여 수준 이하인 포켓몬 트레이너를 쓰러뜨리면서 여행을 하려고 한다. 지우가 한 지역의 포켓몬 트레이너를 쓰러뜨리지 못한다면 그 지역을 통과할 수 없으며, 포켓몬 트레이너를 쓰러뜨렸다면 그 지역의 포켓몬을 모은 후 상하좌우 4방향으로 이동할 수 있다.
지우가
입력
첫 번째 줄에는 양의 정수
다음
다음
마지막
만약 첫 번째 숫자가 1이라면, 그것은 타입 1을 나타내고, 다음 3개의 정수는 각각
X[q], Y[q], query_P[q] 를 나타낸다.이 정보는
(X[q], Y[q]) 지역의 트레이너가query_P[q] 타입의 포켓몬으로 교체한다는 의미이다.1 ≤ query_P[q] ≤ 50,000 를 만족한다.
만약 첫 번째 숫자가 2라면, 그것은 타입 2를 나타내고, 다음 3개의 정수는 각각
X[q], Y[q], query_L[q] 를 나타낸다.이 질문은 지우가
(X[q], Y[q]) 지역에서 시작하여 레벨이query_L[q] 이하인 포켓몬 트레이너를 쓰러뜨릴 수 있을 때, 얼마나 많은 종류의 포켓몬을 얻을 수 있는지 물어보는 질문이다1 ≤ query_L[q] ≤ 10^9 를 만족한다.
출력
타입 2의 질문에 대해서, 지우가 얼마나 많은 종류의 포켓몬을 얻을 수 있는지 한 줄에 하나씩 출력한다.
예제 #1
1 5 5
1 2 3 4 5
1 1 2 1 2
2 2 1 2
2 1 1 4
2 4 1 3
1 3 1 1
2 3 1 4
1
2
0
1
예제 #2
1 5 5
1 2 3 4 5
3 4 3 2 5
2 3 1 3
2 1 1 5
2 4 1 2
1 4 1 4
2 3 1 5
2
4
0
3
예제 #3
3 3 5
1 4 3
11 2 7
5 10 6
1 1 1
2 1 2
1 2 1
2 2 1 6
2 2 3 10
2 3 2 3
1 2 2 2
2 2 1 4
1
2
0
2
예제 #4
3 3 5
1 4 3
11 2 7
5 10 6
6 3 3
4 6 4
9 4 9
2 2 1 6
2 2 3 10
2 3 2 3
1 2 2 7
2 2 1 4
2
4
0
3
로그인해야 코드를 작성할 수 있어요.