문제 1049 소수 찾기(S)
각 노드에 정수의 값을 가지는 이진트리가 있다. 다음 예를 보자.
위 그림과 같이 주어진 이진트리의 노드 번호(빨간색)는 루트가 1이고 너비우선탐색의 순서대로 번호가 부여된다(같은 레벨에서는 왼쪽에서 오른쪽으로 번호가 부여됨). 그리고 각 노드는 하나의 정수 값을 가진다. 위 그림에서는 1번 노드의 값은 7이고 3번 노드의 값은 9이다.
노드 번호 기준으로 1번 노드 왼쪽에 있는 노드들은 2, 4, 5, 8 이다. 즉 현재 트리의 왼쪽 서브트리의 모든 노드들은 자신의 왼쪽에 위치한다고 정의한다. 같은 예로 3번 노드의 오른쪽에 존재하는 노드는 7번 노드 하나 뿐이다.
그런데 각 방향으로 자신의 자식 노드에 대해서만 방향이 있는 것이 아니라 부모노드 쪽으로도 방향이 있다. 예를 들어 2번 노드의 오른쪽에 존재하는 노드는 1, 5, 3, 6, 7번 노드로 모두 5개의 노드가 존재한다. 그리고 가장 왼쪽에 존재하는 노드는 4번 노드이고 가장 오른쪽에 존재하는 노드는 7번 노드이다.
이와 같이 노드의 위치를 정의할 때, 임의의 노드 번호 a, b에 대해서 더 왼쪽에 있는 번호를 l, 오른쪽에 있는 번호를 r이라 하면 [l, r]에 존재하는 소수의 번호는 다음과 같이 구할 수 있다.
예를 들어 a, b가 3, 2라면 이 값은 2가 더 왼쪽에 있는 노드이므로 [2, 3]구간을 나타내며, 이 구간에 존재하는 노드는 2번 노드와 3번 노드를 포함하여 5, 1, 6번 노드로 모두 5개의 노드가 존재한다. 이 노드들 중 소수는 다음 그림과 같이 2번 노드(2), 5번 노드(5), 1번 노드(7), 6번 노드(2)까지 모두 4개 존재한다.
즉, [2, 3] = 4이다. 이와 같이 이 문제에서는 임의의 구간에 대해서 소수의 개수를 구하는 것이 목적이다. 그리고 임의의 노드의 값을 변경할 수도 있어야 한다. 예를 들어 7번 노드의 값을 5로 변경하면 다음 그림과 같이 트리가 바뀐다.
이와 같이 특정 구간의 소수의 개수를 구하는 명령을 1, 특정 노드의 값을 바꾸는 명령을 2라고 할 때, 주어진 트리에서 나타나는 명령을 순서대로 해결하는 프로그램을 작성하시오.
첫 번째 줄에 노드의 수 n이 입력된다.
두 번째 줄에 n개의 노드의 값이 각각 공백으로 구분되어 입력된다(1 <= 노드의 값 <= 10,000).
세 번째 줄부터 n-1줄에 걸쳐서 부모 노드의 번호와 자식 노드의 번호, 위치 정보가 공백으로 구분되어 입력된다. 이 때 왼쪽 자식이라면 세 번째 값은 “L”이 입력되고 오른쪽 자식이라면 “R”이 입력된다.
네 번째 줄에 명령의 수 q가 입력된다.
다섯 번째 줄부터 q줄에 걸쳐서 명령이 입력된다.
각 명령은 1또는 2로 시작되며 1일 경우에는 노드 번호 a, b가 공백으로 구분되어 입력된다.
명령의 값이 2일 경우에는 노드의 번호와 바꾸고자 하는 정수값이 입력된다.
(n, q <= 10,000)
1번 명령에 대한 결과를 출력한다. 2번 명령은 트리의 내용을 바꾸되 결과를 출력하지는 않는다.
8
7 2 9 1 5 2 1 3
1 2 L
1 3 R
2 4 L
2 5 R
3 6 L
3 7 R
4 8 R
3
1 2 3
2 7 5
1 7 2
4
5
*첫 번째 명령은 소수 개수를 구하는 명령으로서 [2, 3]구간에 존재하는 소수의 개수인 2를 출력한다.
*두 번째 명령은 값을 바꾸는 명령으로서 7번 노드의 값을 5로 바꾼다(출력은 하지 않는다).
*세 번째 명령은 소수 개수를 구하는 명령으로서 [2, 7]구간에 존해는 소수(7, 2, 5, 2, 5)의 개수인 5를 출력한다.