Informatica Online Judge

  지하철 연구 [1964 / 07AC]

Time Limit(Test case) : 5000(ms)
Number of users who solved : 1   Total Tried : 4


The Champion of this Problem (C++) : gs17082 - 482ms / 3146byte
My Best Submission (C++) : N/A

[CCC 2017]

Background

어떤 광역시에는 특이한 지하철 시스템이 운영되고 있다.

$n$개의 역이 $m$개의 철로로 연결되어 운영되고 있는데, 각 역은 $1$개의 노선에만 속하고, 각 노선에는 적어도 $1$개의 역으로 구성되어있으며, 각 노선은 원형으로 연결되어있다.

같은 노선의 어떤 $s$번 역의 다음 역 번호는 그 번호보다 크고, 그 노선의 가장 큰 번호 역 다음에는 가장 작은 번호의 역이 연결되어있다.

광역시 연구팀에서는 자원봉사자들을 이용해 지하철 노선 시스템의 운송량 테스트를 수행하고 있다. 각 $i$번 역에 $A_i$명의 승객들이 있는 상태에서 테스트가 시작되며, 자원봉사자들은 테스트가 수행되는 동안 자신이 담당하는 역을 떠나지 않는다.

광역시 연구팀에서는 테스트가 수행되는 과정에서 q개의 주문을 자원봉사자들에게 보낸다.

주문은 $2$가지로 이루어지는데, 그 중 한 가지는 $i$번부터 $j$번 역에 있는 모든 승객의 수를 계산하는 것이고, 다른 한 가지는 $x$번 노선의 지하철들을 모두 다음 역으로 이동시키는 것이다.

연구팀의 연구 수행을 도와보자.

Input

첫 줄에는 $n$, $m$, $q$가 공백을 두고 입력된다.

두 번째 줄에는 각 $1$부터 $n$번역이 속하는 각각의 라인이 공백을 두고 입력된다.

세 번째 줄에는 테스트를 시작할 때, $1$번 역부터 $n$번 역까지 있는 승객의 수($A_i$)가 공백을 두고 입력된다.

그 다음 $q$개의 줄에는 다음과 같은 형태로 연구팀의 주문이 입력된다.:

  • $1$ $i$ $j$ : $i$번 역부터 $j$번 역까지 모든 승객의 수를 출력
  • $2$ $x$ : $x$번 노선 전체를 한 역만큼 이동시킴



[입력값의 정의역]

$1≤m≤n≤150,000$
$1≤q≤150,000$
$1≤A_i≤7,000$
$1≤i≤j≤n$
$1≤x≤m$

Output

연구팀의 주문에 따라 이동시키고 승객 수를 출력한다.

IO Example

입력1
5 2 5
1 2 1 2 2
1 2 3 4 5
1 1 5
2 1
1 3 5
2 2
1 1 3

출력1
15
10
9

설명 : 테스트가 처음 시작할 때의 상태는 다음과 같다.



처음 승객 수는 각 역별로, 1, 2, 3, 4, 5.
1 1 5 : 1번~5번 역 승객 수의 합 출력. 1+2+3+4+5 = 15
2 1 : 1번 노선이 한 칸 이동 하면 3, 2, 1, 4, 5. 으로 상태가 바뀜.
1 3 5 : 3~5번 역 승객 수의 합 출력. 1+4+5 = 10
2 2 : 2번 노선 한 칸 이동. 3, 5, 1, 2, 4 로 인원 수 바뀜.
1 1 3 : 1~3번 역 승객 수의 합 출력. 3+5+1 = 9

입력2
3 1 7
1 1 1
114 101 109
1 1 1
2 1
1 1 1
2 1
1 1 1
2 1
1 1 1

출력2
114
109
101
114

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]