일방통행 시티 > 문제은행



문제은행

3208 : 일방통행 시티

제한시간: 2000 ms    메모리제한: 256 MB
해결횟수: 0 회    시도횟수: 13 회   



정올국 외곽 지역에는 일방통행 시티라는 도시가 있다.

 

일방통행 시티라는 지명에 걸맞게, 이 지역은 모든 주도로가 일방통행이다. 구체적으로는, 1번 마을부터 n번 마을까지가 있는데, 각 i번째 마을은 i+1번째 마을로 향해 갈 수 있는 일방 통행 도로가 있고, 예외적으로 n번 마을만 1번 마을로 일방통행으로 연결 되어 있다. 각 도로들의 길이는 모두 다르다. 즉, 기본적으로 고리 모양의 도시이다.

 

이 지역 사람들은 지나칠 정도로 여유로운 것을 좋아하는데, 그들의 하루 일과는 자기 마을에서 도로를 따라 갈 수 있는 가장 먼 곳으로 이동하면서 주변 경치를 즐기는 것이다.

 

일방통행 시티의 시장인 태구는 매달 다음 3가지 중 한 가지 개발사항을 추진한다.

 

  • 1 x w : x번 마을에서 가장 먼 마을을 y라고 하자. y로부터 길이 w의 도로를 만들고, 그 끝에 새로운 마을을 짓는다.
  • 2 x w: x번 마을에 길이 w의 도로를 만들고, 그 끝에 새로운 마을을 짓는다.
  • 3 x: x번 마을에서 가장 먼 마을을 y라고 하자. y마을을 철거하고, y마을로 가는 도로도 철거한다. 단 이 정책으로 1번부터 n번 마을은 사라지지 않음을 보장한다.

 

태구 시장은 또한 각 마을로부터 가장 먼 마을간의 거리도 알고 싶었다. 그래서 다음과 같은 조사를 하기도 한다.

 

  • ​4 x: x번 마을에서 가장 먼 마을을 y라고 하자. x와 y간의 거리를 알아본다.

 

 

태구의 오른팔인 당신은, 일방통행 시티를 시뮬레이트하는 프로그램을 만들기로 하였다. 각 4가지 사항에 대한 일방통행 시티 시뮬레이터를 프로그래밍하라.​ 




첫 줄에 정수 n이 주어지며, n은 마을의 개수이다(1 <= n <= 105)

다음 한 줄에 n개의 정수가 주어지며, 처음 (n-1)개의 정수는, i번째 정수의 경우, i번 마을에서 i+1번 마을까지의 거리이다. 마지막 n번째 정수는 n번 마을에서 1번 마을간의 거리이다. 각 거리는 1이상 109 이하이다.

다음 줄에 m이 주어지며, m은 시뮬레이터에 들어오는 지시사항의 개수이다. (1 <= m <= 105)

다음 각 m 줄마다 1 x w, 2 x w, 3 x, 4 x; 이 4가지 지시사항 중 하나가 들어온다.

w는 모두 1이상 109이하이다. x는 1이상 n이하이다.(즉, 새로 지어진 마을이 문제시되는 경우는 없다.)
문제에도 설명했듯이, 3 x의 경우 x에서 가장 먼 마을이 원래 존재했던 n개의 마을인 경우는 입력으로 주어지지 않는다.



4 x의 지시사항이 들어올 때마다, 그 답을 출력하라.


5
1 1 1 1 1
4
1 1 5
4 2
3 2
4 2
8
4


1 1 5: 1번에서 가장 먼 마을은 5번 마을이다. 5번 마을로부터 길이 5의 도로를 만들고, 새로운 마을을 만든다. 편의상 이 마을을 6번 마을이라고 하자.
4 2: 2번 마을에서 가장 먼 마을인 6번 마을간의 거리인 8을 출력한다.
3 2: 2번 마을에서 가장 먼 마을인 6번 마을을 철거한다.
4 2: 2번 마을에서 가장 먼 마을인 1번 마을간의 거리인 4를 출력한다.






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.