레이팅 미적용설명
농부 존은 \(N\)개(\(1\le N\le 10^5\))의 농장을 운영하고 있으며, 편의상 \(1\ldots N\)으로 번호가 붙어 있다. 처음에는 농장들을 서로 연결하는 도로가 없고, 모든 농장은 활발히 우유를 생산하고 있다.
경제의 역동적인 특성 때문에, 농부 존은 \(Q\)개(\(0\le Q\le 2\cdot 10^5\))의 업데이트 연산 열에 따라 농장에 변화를 주어야 한다. 업데이트 연산은 세 가지 형태 중 하나이다.
- (D x) 활성 농장 \(x\)를 비활성화하여 더 이상 우유를 생산하지 않게 한다.
- (A x y) 두 활성 농장 \(x\)와 \(y\) 사이에 도로를 추가한다.
- (R e) 이전에 추가된 \(e\)번째 도로를 제거한다(\(e = 1\)은 처음으로 추가된 도로이다).
활발히 우유를 생산하고 있거나, 일련의 도로를 통해 다른 활성 농장에 도달할 수 있는 농장 \(x\)를 "의미 있는(relevant)" 농장이라고 부른다. 각 농장 \(x\)에 대해, \(i\)번째 업데이트 이후 \(x\)가 의미 있는 농장이 되는 최대 \(i\)(\(0\le i\le Q\))를 계산하라.
출제자: Benjamin Qi
제약
배점
- 테스트 2-5는 \(N\le 10^3\), \(Q\le 2\cdot 10^3\)을 만족한다.
- 테스트 케이스 6-20은 추가 제약이 없다.
출제자: Benjamin Qi
입력 형식
입력의 첫째 줄에 \(N\)과 \(Q\)가 주어진다. 다음 \(Q\)개의 줄에 다음 형태 중 하나의 업데이트가 각각 주어진다.
D x
A x y
R e
R 형태의 업데이트에서 \(e\)는 지금까지 추가된 도로의 수 이하이며, R 형태의 어떤 두 업데이트도 같은 \(e\) 값을 갖지 않음이 보장된다.
출력 형식
\(0\ldots Q\) 범위의 정수를 하나씩 담은 \(N\)개의 줄을 출력한다.
예제 1
입력
5 9
A 1 2
A 2 3
D 1
D 3
A 2 4
D 2
R 2
R 1
R 3출력
7
8
6
9
9설명
In this example, roads are removed in the order \((2,3), (1,2), (2,4)\).
- Farm \(1\) is relevant just before \((1,2)\) is removed.
- Farm \(2\) is relevant just before \((2,4)\) is removed.
- Farm \(3\) is relevant just before \((2,3)\) is removed.
- Farms \(4\) and \(5\) are still active after all queries. Therefore they both stay relevant, and the output for both should be \(Q\).
문제 정보
태그