この問題はかなり苦労しました。というのも、動的SegmentTreeで解こうとすると空間計算量が非常に厳しくなるからです。
ですが、よく考えると動的SegmentTreeの空間計算量がO(log|区間の幅|)というのは変な気がします。なので少し考えてみたら、平衡二分木を使うことでO(log|クエリ数|)(もちろんクエリ数 < 区間の幅とする)に落とせたのでメモします。
この問題の想定解はsetを使いますが、もちろんそれではなく、あくまで動的SegmentTreeとしてsetを使ったという話です。
基本的には葉にのみ値をもたせる木を考えます。 普通のSegmentTreeと違うのは、葉が長さ1より大きい区間を持つかもしれないということです。なので、if (n->sz == 1)では葉の判定ができず、ノードごとにそれが葉であるかというフラグを持たせる必要があります。
クエリ処理ですが、区間[l, r)にアクセスしたいときは、inscut(l)とinscut(r)をしておいてからクエリを投げるという方針で考えます。inscut(k)とは、木の葉が [..., k), [k, ....) となるように区切りを入れる関数です。
これは木を葉まで潜って行って、葉に当たったら[0, sz)を[0, k), [k, sz)に変更するだけです。これは平衡二分木のinsertで実現できます。
この関数さえ作れば、あとはよしなになんとかなります。というのも、この関数を使っておけば、区間の端が葉の途中に来るということがなくなるので、普通にSegTreeのように木を潜るだけでクエリが解決できるようになるからです。
