Loading...
$N$개의 정수로 이루어진 배열이 주어진다. 다음 두 종류의 쿼리를 처리하는 프로그램을 작성하라. 이 문제는 쿼리 1이 실행될 때마다 기존 배열을 변경하는 것이 아니라 새로운 버전의 배열을 만들어내는 영속 세그먼트 트리(Persistent Segment Tree)를 구현하여 해결할 수 있다.
1 v i x: $v$번 버전의 배열에서 $i$번째 원소를 $x$로 바꾼 새로운 버전을 만든다. 새로운 버전의 번호는 이전까지 만들어진 가장 큰 버전 번호에 1을 더한 값이 된다.2 v i: $v$번 버전의 배열에서 $i$번째 원소를 출력한다.초기 배열은 0번 버전이다.
첫째 줄에 배열의 크기 $N$이 주어진다.
둘째 줄에 초기 배열의 $N$개의 원소가 공백으로 구분되어 주어진다.
셋째 줄에 쿼리의 개수 $Q$가 주어진다.
넷째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.
쿼리 2가 주어질 때마다, 해당 버전의 배열에서 $i$번째 원소를 한 줄에 하나씩 출력한다.
5
3 1 4 1 5
4
1 0 2 10
2 0 2
2 1 2
2 1 3
1
10
4
3
1 2 3
3
1 0 1 9
2 0 1
2 1 1
1
9