平方分割を用いて空間 \(O(N \sqrt N)\)、時間 \(O((N+Q) \sqrt N)\) の解法です。

方針として、各数列を「もとの数列の \([l, r)\) 区間にある、値が \([u, v) \) に含まれるような長さ \(len\) の数列」として、\((l, r, u, v, len)\) というタプル型で管理することを考えます。各クエリごとに、操作をする数列と新しい数列のタプルを比較的高速に計算できればよいです。

クエリ処理のために、事前にブロックサイズ \(B\) ごとに「このブロック内の \(u\) 以上の値の個数」を前計算しておきます。（これは、累積和で \(O(N^2 / B)\) で計算可能です。）以下、各クエリごとにどのように処理をするのかを考えます。

タイプ1のクエリ

もとの数列のタプルが \((l, r, u, v, len)\) であったとします。\(len < x\)のようなケースはあらかじめ弾いておくことにすると、結局「\(l < rn < r\) を満たすような \(rn\) であって、\([l, rn)\) に含まれる 値が\([u, v)\) にあるような数の個数がちょうど \(x\) 個であるようなものを求めよ」というタイプの問題となります。これは、事前に計算したブロックごとの累積和を用いて \(rn = l\) から順に 1 ブロック進めるなら進む、そうでないなら \(rn\) を一つ増やす操作を繰り返して \(rn\) を求めることができます。求めた \(rn\) を使って、もとの数列を \((l, rn, u, v, x)\)、新しい数列を \((rn, r, u, v, len - x)\) のように更新すればよいです。

ブロックを進める操作はたかだか \(O(N / B)\) 回、値を1つ進める操作も 高々 \(2 B\) 回で抑えられるため、このクエリ処理は 1 つあたり \(O( B + N / B)\) です。

タイプ2のクエリ

もとの数列のタプルが \((l, r, u, v, len)\) であったとします。\(x < u\) や \(v < x\) のようなケースは事前に処理することとして、結局 \([l, r)\) 区間内の値 \([u, x+1)\)の数の個数を求めるクエリを高速に処理できればよいです。これは、事前に計算した累積和の配列によって容易に \(O(N / B + B)\) で行うことができます。求めた値を \(len'\)として、もとの数列を \((l, r, u, x+1, len')\)、新しい数列を \((l, r, x+1, v, len - len')\) のように更新すればよいです。

まとめ

バケットサイズ \(B = \sqrt N\) と取ることで、タイプ1・タイプ2のいずれも 1 クエリあたり \(O(\sqrt N)\) で処理することができたため、前計算も含めて結局この問題を時間計算量あたり \(O((N + Q)\sqrt N)\)で解くことができます。

ただし、メモリを \(O(N \sqrt N)\) 使う場合、MLEに注意する必要があり、また、メモリアクセスが律速となりTLの定数倍が非常に厳しいことがあります。（特に低速な言語では AC が難しいと思います。）例えば以下のような工夫によって定数倍を改善することで AC を得ることができます。

• 可変長配列（std::vector等）ではなく、固定長配列（std::array等）を用いる
• 累積和の配列を（64 bit 整数型ではなく）32 bit 整数型で管理する
• バケットサイズ \(B\) を \(\sqrt N \simeq 500\) よりも少し大きめの値（\(1000\) 前後の値）にとり、メモリが巨大になることを避ける