시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 0 0 0.000%

문제

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

  • 1 y z: a[y] = z 를 수행한 후 F(a, b) 를 출력한다. (1 ≤ y ≤ n, 1 ≤ z ≤ 105)
  • 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: 수열 [bp, bp+1, ..., bq, br, br+1, ..., bs] 가 b의 연속된 부분 수열 중 하나이면 "yes", 아니면 "no" 를 출력하라. (1 ≤ p ≤ q ≤ m, 1 ≤ r ≤ s ≤ m)

a[l..r] 은 [al, al+1, ..., ar] 인 부분수열이다. 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 ≤ 105)

다음 줄에 n개의 정수 a1, a2, ..., an 이 주어진다. (1 ≤ ai ≤ 105)

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

다음 줄에 m개의 정수 b1, b2, ..., bm 이 주어진다. (1 ≤ bi ≤ 105)

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

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

출력

각각의 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

10
1 2 3 3 3 1 2 3 2 1
3
1 3 1
10
3 1 3
4 3 3 2 2
2 2 10
1 3 2
2 7 9
2 7 10
2 3 9
2 2 8
1 7 1
1 4 2

예제 출력 1

1
yes
1 2
1 3
0 3
1 1
1 1
1 1
2 1
2 1

출처

  • 문제를 번역한 사람: koosaga