以下のようにして得られる数列 \(B\) を考えます．

• はじめ \(B=(0)\) である．
• \(i=1,\dots,Q\) に対して順に，\(i\) 番目のクエリに応じて以下の操作を行う．
  • クエリが 1 x のとき，\(B\) の \(x\) の直後に \(i\) を挿入する．
  • クエリが 2 x y のとき，何もしない．

\(B\) は stack などにより計算できます．

\(B\) の要素である \(i\) に対し，\(P_i\) を \(B_{P_i}=i\) を満たす整数とします．

このとき元の問題は以下のように言い換えられます．

• 長さ \(Q+1\) の数列 \(V\) があり，はじめ \(V=(0,0,\dots,0)\) である．
• \(i=1,\dots,Q\) に対して順に，\(i\) 番目のクエリに応じて以下の操作を行う．
  • クエリが 1 x のとき，\(V_{P_i}=i\) とする．
  • クエリが 2 x y のとき，\(p=\min(P_x,P_y),q=\max(P_x,P_y)\) として \(V_{p+1}+V_{p+2}+\cdots+V_{q-1}\) を出力し，\(V_{p+1},V_{p+2},\dots,V_{q-1}\) をすべて \(0\) にする．

遅延セグメント木を用いたり，\(V\) のうち \(0\) でない要素の位置を管理したりすることで \(O(Q\log Q)\) 時間などで解くことができます．

• 実装例(C++, 遅延セグメント木)
• 実装例(C++, std::set)
• 実装例(C++, セグメント木)