빅 데이터 순열

시간 제한15초메모리 제한2048 MB

요약

배열 a의 값을 바꾸는 갱신과 구간 질의가 주어집니다. 질의마다 [l, r] 안에서 a[j+1]=b[a[j]]가 이어지고 값 x를 포함하는 가장 긴 부분 구간의 길이를 구합니다.

난이도: 어려움10점 중 9점
유형: 세그먼트 트리, 배열, 그래프
정답자: 아직 제출이 없습니다

문제

길이가 $n$ 인 수열 $a_1, \ldots, a_n$ 과 순열 $b_1, \ldots, b_n$ 이 주어진다. 다음 두 가지 연산을 $m$ 번 처리한다.

수정 연산: $x$ 와 $y$ 가 주어진다. $a_x$ 를 $y$ 로 바꾼다.
조회 연산: $\ell$ , $r$ , $x$ 가 주어진다. 구간 $[\ell, r]$ 의 부분 구간 $[\ell', r']$ (단, $\ell \le \ell' \le r' \le r$ ) 중에서 모든 $\ell' \le j < r'$ 에 대해 $a_{j+1} = b_{a_j}$ 이고, $\ell' \le i \le r'$ 을 만족하는 어떤 $i$ 에 대해 $a_i = x$ 인 가장 긴 구간을 찾는다. 그 구간의 길이 $r' - \ell' + 1$ 만 출력한다. 그런 구간이 없으면 $0$ 을 출력한다.

입력

첫째 줄에 $n$ 과 $m$ 이 주어진다 ( $1 \le n, m \le 10^6$ ). 둘째 줄에는 $a_1, \ldots, a_n$ 이 주어진다 ( $1 \le a_i \le n$ ). 셋째 줄에는 $b_1, \ldots, b_n$ 이 주어진다 ( $1 \le b_i \le n$ , 모든 $b_i$ 는 서로 다르다). 이후 $m$ 개의 줄에 연산이 하나씩 주어진다. 수정 연산은 1 x y 형태이고, 조회 연산은 2 l r x 형태이다 ( $1 \le x, y \le n$ , $1 \le \ell \le r \le n$ ). 조회 연산은 적어도 하나 주어진다.

출력

각 조회 연산마다 답을 한 줄에 출력한다.

예제1

예제 1

입력

8 10
1 4 7 3 8 2 4 7
5 4 8 7 1 6 3 2
2 6 6 2
2 8 8 7
1 4 3
2 6 8 3
2 4 4 3
2 4 4 3
2 6 8 4
2 5 6 2
2 1 8 1
2 1 1 6

예상 출력