17937번 - 수열과 쿼리 34

길이가 각각 n, m이며 양의 정수로 이루어진 두 수열 a, b가 주어질 때, 아래의 쿼리를 수행하는 프로그램을 작성하시오. 모든 인덱스는 1-based 이다.

• 1 y z: a[y] = z 를 수행한 후 F(a, b) 를 출력한다. (1 ≤ y ≤ n, 1 ≤ z ≤ 10⁵)
• 2 y z: F(a[y..z], b) 를 출력한다. (1 ≤ y ≤ z ≤ n)
• 3 y z: f(b[y..m], b[z..m]) 를 출력한다. (1 ≤ y, z ≤ m)
• 4 p q r s: 수열 [b_p, b_p+1, ..., b_q, b_r, b_r+1, ..., b_s] 가 b의 연속된 부분 수열 중 하나이면 "yes", 아니면 "no" 를 출력하라. (1 ≤ p ≤ q ≤ m, 1 ≤ r ≤ s ≤ m)

a[l..r] 은 [a_l, a_l+1, ..., a_r] 인 부분수열이다. b에 대해서도 유사하게 정의된다.

두 수열 x, y에 대해:

• f(x, y) 는 x와 y의 최대 공통 접두사 (Longest common prefix) 의 길이이다.
• F(x, y) 는 두 정수의 쌍 (p, q)로, p는 모든 x의 접미사 (suffix) z에 대해 f(z, y) 의 최댓값, q는 그러한 최댓값을 이루는 z의 개수를 뜻한다.

첫 번째 줄에 a의 길이 n이 주어진다. (1 ≤ n ≤ 10⁵)

다음 줄에 n개의 정수 a₁, a₂, ..., a_n 이 주어진다. (1 ≤ a_i ≤ 10⁵)

다음 줄에 b의 길이 m이 주어진다. (1 ≤ m ≤ 10⁵)

다음 줄에 m개의 정수 b₁, b₂, ..., b_m 이 주어진다. (1 ≤ b_i ≤ 10⁵)

다음 줄에 쿼리의 개수 q가 주어진다. (1 ≤ q ≤ 10⁵)

이후 q개의 줄에 위에서 설명한 것과 같은 쿼리가 주어진다.