Wavelet Matrix というデータ構造を使うことで \(O(N\log N+Q(\log N)^2)\)で解くことができます。

Wavelet Matrix を用いると、長さ \(N\) の固定された数列に対して、\(O(N\log N)\) の前計算の下、「区間 \([l,r)\) に値が \(x\) 未満のものは何個あるか？」というクエリに \(O(\log N)\)で答えることができます。

操作によって新たに作られる数列は必ず「元の数列の区間 \([l,r)\)、値 \([x,y)\) の要素のみからなる数列」として表すことができます。したがって、この \(l,r,x,y\) を管理することにすれば、\(t=1\) のクエリは二分探索により \(O((\log N)^2)\)、\(t=2\) のクエリは \(O(\log N)\) で処理することができます。