JOI Open 2018 #3- Collapse > 문제은행 : 정보올림피아드&알고리즘


4685 : Collapse

제한시간
6000 ms   
메모리제한
512 MB   
해결횟수
1 회   
시도횟수
1 회   

문제

JOI 왕국에는 직선 형태의 깊은 계곡을 따라 N개의 마을이 있다.

마을은 바다에서부터의 거리 순서대로 0, 1, ... , N - 1 까지의 번호가 붙어 있다.

 

JOI 왕국 과학 위원회의 의장인 준혁이는, 마을 사이를 잇는 케이블을 통해 양방향 통신을 유지하려고 계획중이다.

현재, JOI 왕국에는 케이블이 하나도 없다.

 

준혁이는 C일 동안의 케이블 건설 계획이 있다.

i + 1일(0 ≤ i ≤ C − 1)의 계획은 세 정수 Ti, Xi, Yi로 이루어져 있다.

- Ti = 0일 때, 마을 Xi와 마을 Yi를 잇는 케이블을 건설한다. (i + 1일이 시작할 때, 마을 Xi와 마을 Yi를 잇는 케이블이 존재하지 않음이 보장된다.)

- Ti = 1일 때, 마을 Xi와 마을 Yi를 잇는 케이블을 철거한다. (i + 1일이 시작할 때, 마을 Xi와 마을 Yi를 잇는 케이블이 존재함이 보장된다.)

 

JOI 왕국에서는 절벽 붕괴가 자주 일어난다.

마을 x(0 ≤ x ≤ N − 2)와 마을 x + 1 사이에 붕괴가 일어났다면, x 이하의 번호를 가진 마을과 x + 1 이상의 번호를 가진 마을 사이에 이어진 모든 케이블이 끊어진다.

붕괴가 일어날 시, JOI 왕국은 몇 개의 마을을 골라 기지국을 건설한다.

기지국은 어떤 마을에서 시작하더라도 유효한 케이블을 이용하여 도달할 수 있도록 건설되어야 한다.

 

준혁이는 건설 기간 동안 붕괴가 일어났을 때 몇 개의 기지국을 건설해야 하는지 구하여야 한다.

준혁이는 Q개의 상황이 궁금하다: j + 1번째 상황은 두 정수 Wj, Pj로 이루어진다.

이는 준혁이가 Wj + 1번째 날에 마을 Pj와 마을 Pj + 1 사이에 붕괴가 일어났을 시 필요한 기지국의 개수의 최솟값을 알고싶어한다는 뜻이다.

 

당신은 준혁이의 비서로서, 준혁이가 궁금해하는 각 상황에 대하여 답을 구하는 프로그램을 만들자.​


입력형식

1번 줄 : N C Q

2번 ~ C + 1번 줄 : Ti Xi Yi

C + 2번 ~ C + Q + 1번 줄 : Wj Pj

 

2 ≤ N ≤ 100 000

1 ≤ C, Q ≤ 100 000​ 


출력형식

N개의 줄에 걸쳐 i번째 상황에 대한 답을 출력하여라. 


입력 예

5 8 2
0 0 1
0 1 3
0 2 4
0 4 0
1 1 3
0 0 3
0 1 2
0 4 3
3 1
7 3

출력 예

3
2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP