数列とクエリ 34 - Problem

2つの正の整数列 $a$（長さ $n$）と $b$（長さ $m$）が与えられます。以下のクエリを処理するプログラムを作成してください。すべてのインデックスは 1 から始まります。

1 y z: $a[y] = z$ を実行し、その後 $F(a, b)$ を出力する。（$1 \le y \le n$, $1 \le z \le 10^5$）
2 y z: $F(a[y..z], b)$ を出力する。（$1 \le y \le z \le n$）
3 y z: $f(b[y..m], b[z..m])$ を出力する。（$1 \le y, z \le m$）
4 p q r s: 数列 $[b_p, b_{p+1}, \ldots, b_q, b_r, b_{r+1}, \ldots, b_s]$ が $b$ の連続部分列であるならば "yes" を出力し、そうでなければ "no" を出力する。（$1 \le p \le q \le m$, $1 \le r \le s \le m$）

$a[l..r]$ は部分列 $[a_l, a_{l+1}, \ldots, a_r]$ を表す。$b$ についても同様に定義される。

2 つの数列 $x, y$ に対して:

$f(x, y)$ は $x$ と $y$ の最長共通接頭辞の長さを表す。
$F(x, y)$ は整数の組 $(p, q)$ であり、$p$ は $x$ のすべての接尾辞 $z$ に対する $f(z, y)$ の最大値、$q$ はその最大値を達成する $z$ の個数である。

1 行目には整数 $n$ が与えられる。これは $a$ の長さである。（$1 \le n \le 10^5$）

次の行には $n$ 個の整数 $a_1, a_2, \ldots, a_n$ が与えられる。（$1 \le a_i \le 10^5$）

次の行には整数 $m$ が与えられる。これは $b$ の長さである。（$1 \le m \le 10^5$）

次の行には $m$ 個の整数 $b_1, b_2, \ldots, b_m$ が与えられる。（$1 \le b_i \le 10^5$）

次の行には整数 $q$ が与えられる。これはクエリの個数である。（$1 \le q \le 10^5$）

続く $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

QOJ.ac