\(P\) が固定されているときの解法

まず、\(P\) の更新クエリは一旦忘れて、\(P\) を固定したときの問題を考えます。

数列 \(A\) に対する更新操作は以下の式で定義されています。

\[A_j \leftarrow \left\lfloor \frac{A_{j-1}A_{j+1}}{A_j} \right\rfloor + 1\]

これは以下のように書き換えることができます。

\[A_j \leftarrow \left\lceil \frac{A_{j-1}A_{j+1} + 1}{A_j} \right\rceil\]

ここで、一旦天井関数を外した以下の操作を考えます。

\[A_j \leftarrow \frac{A_{j-1}A_{j+1} + 1}{A_j}\]

後の議論で示されるように、この操作において \(A_{j-1}A_{j+1} + 1\) は常に \(A_j\) で割り切れ、\(A_j\) は常に整数となります。 この事実を認めると、天井関数を外した新しい操作の結果は元の操作と常に一致するため、以降はこの新しい操作について答えを求めればよいことになります。

ここで、無限に広がる二次元グリッドを考え、グリッド上のマス \(S_1, \ldots, S_N\) を以下のように定めます。(\((1,0)\) を右方向、\((0,1)\) を上方向とします。)

• \(S_1 = (1,-1)\) とする。
• \(j\) よりも先に \(j-1\) が操作されるとき (\(P^{-1}_{j-1} < P^{-1}_j\) のとき)、\(S_j = S_{j-1} + (1,0)\) (\(S_{j-1}\) の右のマス) とする。
• \(j-1\) よりも先に \(j\) が操作されるとき (\(P^{-1}_{j-1} > P^{-1}_j\) のとき)、\(S_j = S_{j-1} + (0,-1)\) (\(S_{j-1}\) の下のマス) とする。

便宜上、\(S_0 = (1,0), \ S_{N+1} = S_N + (1,0)\) とします。

\(A\) への操作に応じて、これらのマスを動かしながら、二次元グリッド上に数を書き込んでいきます。 はじめに、各マス \(S_i\) に \(1\) を書き込んでおきます。 さらに、\(A_j\) に操作を行うたびに、以下の操作を行うことにします。

• \(S_j\) を \(S'_j = S_j + (1,1)\) (右上のマス) に置き換え、新しい \(S_j\) に更新後の \(A_j\) の値を書き込む。

ただし、\(A\) への操作を \(N\) 回終えて \(j\) が一巡するたびに、 \(S_0, \ S_{N+1}\) を \(S_0 + (1,1), \ S_{N+1} + (1,1)\) に置き換え、新しい \(S_0, \ S_{N+1}\) に \(1\) を書き込むという操作をすることにします。

この操作を無限に繰り返してグリッドに数を書き込んでいきます。 マス \((i,j)\) に書き込まれた値を \(B_{i,j}\) とします。 初期状態のマス \(S_j\) の座標を \((a_j, b_j)\) とすれば、\(A\) に対して操作を \(NK\) 回行った後の \(A_x\) の値は \(f(P, K, x) = B_{a_x+K, b_x+K}\) となります。

\(A_j\) に対して操作が行われるとき、\(S_j, S_{j+1}, S_{j-1}, S'_j\) は \(2 \times 2\) の正方形をなすため、値が書き込まれた範囲では以下の等式が成り立つことがわかります。

\[B_{i,j} B_{i+1,j+1} = B_{i+1,j} B_{i,j+1} + 1\]

また、以下のように 値を書き込む範囲を拡張しても、この等式は \(B\) が定まっている範囲で成り立ちます。

• \(B_{x,x} = B_{x+N+3,x} = 0 \ (x \in \mathbb{Z})\)

逆に、以下の条件が成り立っていれば、漸化式によって残りの \(B\) の値を一意に復元することができます。

• \(B_{a_j,b_j} = 1 \ (j = 0, \ldots, N)\)
• \(B_{x,x} = B_{x+N+3,x} = 0 \ (x \in \mathbb{Z})\)

（境界部分を除いて値は常に正となるため、ゼロ除算が発生する可能性はありません。）

次に、\(\{v_i\}_{i \in \mathbb{Z}}\) を \(2\) 次元縦ベクトルの列であって、以下の性質を満たすものとします。

\[ \det(v_i \ v_{i+1}) = 1 \qquad (i \in \mathbb{Z})\]

このとき、\(C_{i,j} = \det(v_j \ v_i)\) と定義すると、行列式の性質を用いることで以下が成り立つことがわかります。

\[C_{i,j} C_{i+1,j+1} = C_{i+1,j} C_{i,j+1} + 1\]

したがって、このようなベクトル列 \(\{v_i\}_{i \in \mathbb{Z}}\) のうち、以下の条件を満たすものが存在すれば、漸化式より値が書き込まれたすべてのマスについて \(B_{i,j} = C_{i,j}\) が成り立ちます。

• \(C_{a_j,b_j} = 1 \ (j = 1, \ldots, N)\)
• \(C_{x,x} = C_{x+N+3,x} = 0 \ (x \in \mathbb{Z})\)

この \(2\) 次元ベクトルの列 \(v_i\) は、具体的に次のように構築することができます。

• \(v_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \ v_1 = \begin{pmatrix} 0 \\ 1 \end{pmatrix}\) とする。
• \(j = 1, 2,\ldots, N+1\) について、以下のように定める。
• \((a_j,b_j) = (a_{j-1}+1,b_{j-1})\) のとき、\(v_{a_j} = v_{a_{j-1}} - v_{b_{j-1}}\) とする。
• \((a_j,b_j) = (a_{j-1},b_{j-1}-1)\) のとき、\(v_{b_j} = v_{b_{j-1}} - v_{a_{j-1}}\) とする。
• \(a_{N+1} - b_{N+1} = N+2\) より、ここまでで \(N+3\) 個の連続した \(v\) の値が定まったことに注意し、\(v_{i+N+3} = -v_i\) となるように \(v\) を拡張する。

この構成により、以下の条件を満たすことが確認できます。

• \(\det(v_i \ v_{i+1}) = 1 \ (i \in \mathbb{Z})\)
• \(C_{a_j,b_j} = 1 \ (j = 1, \ldots, N)\)
• \(C_{x,x} = C_{x+N+3,x} = 0 \ (x \in \mathbb{Z})\)

この構築において、\(v_i\) の成分は常に整数であるため、\(B_{i,j} = C_{i,j}\) も常に整数となり、操作において \(A_j\) の値が常に整数であることが証明されます。 \(v_i\) の値を前計算しておけば、\(f(P,K,x)\) の値を \(O(1)\) で計算することが可能です。

更新クエリ

続いて、\(P\) の更新クエリがある場合を考えます。 ここまでの考察により、\(v_i\) の値を効率的に管理できればよいことがわかります。 \(v_i\) の値は \(P^{-1}_{j-1}\) と \(P^{-1}_j\) の大小関係によって決まります。 \(P_i\) と \(P_j\) を入れ替えると、\(P^{-1}\) の中で対応する値のインデックスが変化しますが、大小関係が変化するのは入れ替えた要素の周辺（最大 \(4\) 箇所）のみであるため、これらについて局所的に更新を行えば十分です。

\(v_i\) の構築手順に着目すると、行列 \((v_{a_j} \ v_{b_j})\) の値は、一つ前の行列 \((v_{a_{j-1}} \ v_{b_{j-1}})\) に適切な \(2 \times 2\) 行列を右から掛けることで得られることがわかります。 したがって、\((v_{a_j} \ v_{b_j})\) の値はこれらの行列の列の prefix product として表現でき、セグメント木を用いることで値の更新および取得を \(O(\log N)\) で行うことができます。

取得クエリの際、目的の座標に対応する \(i\) (\(i \equiv a_j \pmod{N+3}\) または \(i \equiv b_j \pmod{N+3}\)) に対応する \(j\) を求める必要がありますが、これは「\(P^{-1}_{j-1} < P^{-1}_j\) または \(P^{-1}_{j-1} > P^{-1}_j\) となる \(j\) の集合について \(k\) 番目の値を求めるクエリ」に帰着します。 この処理は Binary Indexed Tree 上の二分探索や平衡二分探索木などを用いることで、高速に処理することができます。

以上を適切に実装することで、本問題を全体時間計算量 \(O(N + Q \log N)\) で解くことができます。