\([l,r]\) において

• \(A_l, \dots , A_r\) の最小値( \(p\) とする)
  
• \(l \leq j \leq r\) かつ \(A_j = p\) を満たす \(j\) のうち、最小のもの
  

の \(2\) つの値を保存したSegment Tree を作ります。
\(T_i = 1\) のクエリについては、\(O( \log N)\) で更新することが可能です。
\(T_i = 2\) のクエリについては、列挙すべき \(j\) を \(1\) つ見つけるのに \(O( \log N)\) かかります。したがって、列挙すべき \(j\) の個数の総和を \(MAX (\leq 2 \times 10^5)\) とおくと、\(T_i = 2\) のクエリを合計して \(O((Q_2 + MAX) \log N)\) で解くことができます。
以上まとめると、\(O((N+Q+MAX) \log N)\) で解くことができます。