広場および公園を、それぞれマスおよびマス目と呼ぶことにします。また、行進をシナリオと呼ぶことにします。

オフライン解法

クエリを先読みしてまとめて答えて良いときの解法を提示します。

人とマスを左右に \(M\) 個ずつ増やしておきます。つまり、マス \(-M,-M+1,\dots, N+M-1\) があったとして、はじめはマス \(i\) に人 \(i\) がいるとします。マスにいる人数を答えるときは、人 \(0,1,\dots, N-1\) のみ数えることに注意します。

まず、\(A\) 全体に対するシナリオをシミュレーションします。次のクエリに答えるデータ構造を設計します。

1. 人 \(x\) がいるマスの番号を答える。
2. マス \(x\) にいる人の番号の最小値を答える。
3. マス \(x\) にいる人の番号の最大値を答える。
4. マス \(x\) にいない人をすべてマス \(x\) に \(1\) マスぶんだけ近づける。

移動によって人の相対順序は変わらず、人 \(i+1\) のいるマスと人 \(i\) のいるマスの番号の差は常に \(0\) または \(1\) です。さらに、その差が一度 \(0\) になると、それ以降 \(0\) のままになります。そこで、その差 \(d_i\) を区間和を乗せたセグメント木で管理します。クエリ 1,2,3 はセグメント木上の二分探索で行うことができ、クエリ 4 は 1,2,3 を駆使してセグメント木上の高々 \(2\) 箇所の変更に帰着できます。

\(A\) 全体に対するシミュレーションでは、\(x=A_1,A_2,\dots, A_M\) の順にクエリ 4 を投げることになります。

区間シナリオクエリには、シミュレーションの最中に適切にデータ構造にクエリを投げることで答えることができます。 \((A_L,A_{L+1},\dots, A_R)\) に対するシナリオを \(A[L,R]\) と表します。

シナリオ \(A[L,R]\) での人 \(P\) の行き先を求める

\(x=A_L\) の直前のデータ構造において、マス \(P\) にいる人をクエリ 2 を使って \(1\) 人求め、人 \(y\) とします。人とマスを増やしたことで、そのような人は必ず存在することに注意してください。人 \(y\) の動きをシナリオ \(A[L,R]\) での人 \(P\) の動きと同一視できます。したがって、\(x=A_R\) の直後のデータ構造において \(y\) のいるマスの番号が求める答えとなり、これはクエリ 1 を使って求めることができます。

シナリオ \(A[L,R]\) 終了後のマス \(P\) にいる人数を求める

\(x=A_R\) の直後のデータ構造において、マス \(P\) にいる人の番号の最小値 \(l\) と最大値 \(r\) をクエリ 2,3 を使って求めます。次に \(x=A_L\) の直前のデータ構造において、クエリ 1 を使って人 \(l,r\) のいる位置 \(l',r'\) をそれぞれ求めます。シナリオ \([L,R]\) において終了後にマス \(P\) にいる人の動きを、\(x=A_L\) の直前において位置 \([l',r']\) にいる人の動きと同一視できます。実際のシナリオ \(A[L,R]\) では、はじめは位置 \([1,N]\) に人が \(1\) 人ずついるだけなので、\([l',r'],[1,N]\) の共通部分に含まれる整数の個数が答えになります。

オンライン化

これらのクエリはオンラインで処理することができます。区間シナリオの答えを求める際にはデータ構造を変更しないため、あらかじめ \(A\) 全体に対するシミュレーションを行っておき、その過程の特定の時刻でのデータ構造にアクセスすることができれば十分です。データ構造を永続化すれば良く、上述の解法では永続セグメント木があれば十分です。この解法は \(O((N+M+Q)\log (N+M))\) 時空間で動作します。

余談

クエリオンラインを要求したのは、人とマスを増やさずに、クエリ毎に注目する人をデータ構造に追加していく、平衡二分木を用いた素朴な解法との差別化を図るためです。