버전을 넘나드는 로프
다이아몬드 II의견: 0
처음에 비어 있는 수열이 있다. 이 수열의 상태를 '버전'이라고 부르며, 비어 있는 초기 상태를 버전 \(0\)이라 한다. 다음 세 종류의 연산을 입력 순서대로 처리한다.
-
1 v p x: 버전 \(v\)의 수열을 가져와, \(p\)번째 위치 바로 앞에 값 \(x\)를 삽입한 새로운 수열을 만든다 (\(1 \le p \le L_v + 1\), \(L_v\)는 버전 \(v\)의 길이). 이렇게 만들어진 수열은 새로운 버전이 된다. -
2 v p: 버전 \(v\)의 수열을 가져와, \(p\)번째 원소를 삭제한 새로운 수열을 만든다 (\(1 \le p \le L_v\)). 이렇게 만들어진 수열은 새로운 버전이 된다. -
3 v l r: 버전 \(v\)의 수열에서 \(l\)번째부터 \(r\)번째까지의 원소들에 대한 체크섬을 출력한다 (\(1 \le l \le r \le L_v\)). 이 연산은 새 버전을 만들지 않는다.
버전 번호는 1 또는 2 연산이 수행될 때마다 \(1, 2, 3, \dots\) 순서로 새로 부여된다 (즉 \(k\)번째로 수행된 1/2 연산이 버전 \(k\)를 만든다). 모든 연산은 그 시점까지 이미 존재하는 버전만 참조한다.
체크섬은 다음과 같이 계산한다. 대상 원소들을 위치 순서대로 \(b_1, b_2, \dots, b_m\) 이라 할 때, \(M = 2^{61} - 1\), \(h_0 = 0\), \(h_k = (h_{k-1} \cdot 1000003 + b_k + 1) \bmod M\) 을 차례로 계산하여 \(h_m\)을 출력한다.
\(1 \le Q \le 50{,}000\)
\(0 \le x \le 10^9\)
버전 번호 \(v\), 위치 \(p, l, r\) 는 항상 위 제약을 만족하는 유효한 값이다.
3 연산은 적어도 한 개의 원소가 존재하는 구간에 대해서만 주어진다.
첫 줄에 연산의 개수 \(Q\)가 주어진다.
이어서 \(Q\)개의 줄에 위 형식의 연산이 한 줄에 하나씩 주어진다.
각 3 연산마다 해당 구간의 체크섬을 한 줄에 하나씩 출력한다.
6
1 0 1 5
1 1 2 7
1 2 1 3
3 3 1 3
2 3 2
3 4 1 2
4000030000062
4000020버전0=[]. 연산1: 버전0에 위치1앞에 5 삽입 -> 버전1=[5]. 연산2: 버전1 위치2앞에 7 삽입 -> 버전2=[5,7]. 연산3: 버전2 위치1앞에 3 삽입 -> 버전3=[3,5,7]. 연산4: 버전3 전체[3,5,7]의 체크섬 출력. 연산5: 버전3 위치2(=5) 삭제 -> 버전4=[3,7]. 연산6: 버전4의 [3,7] 체크섬 출력. (옛 버전이 그대로 보존됨)
5
1 0 1 1
1 1 2 2
1 0 1 9
3 2 1 2
3 3 1 1
2000009
10버전1=[1], 버전2=[1,2]. 연산3은 다시 버전0(빈 수열)에서 분기해 버전3=[9]. 연산4: 버전2의 [1,2] 체크섬. 연산5: 버전3의 [9] 체크섬. 버전2는 버전3 생성에 영향받지 않는다.
riseoj 작성
출처 Original
평가 및 의견
버전을 넘나드는 로프
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
버전을 넘나드는 로프