これも没問を蘇生させたものです.
問題原案:uni_kakurenbo
Union-Find に併せて一点取得および区間更新のできるデータ構造を用いることで解けます.
適当なテーブルで,グラフの頂点からの集合の要素への対応を管理します. t=1t = 1t=1 のクエリにおいては,どの要素にも対応しないことを表す値で対象となる区間を更新することで実現できます. 実装例も参照してください.
なお,平衡二分探索木などによって頂点と要素との対応を管理することでも正解できます.
解説:uni_kakurenbo