HHKBプログラミングコンテスト2022 Winter (AtCoder Beginner Contest 282) F - Union of Two Sets (500)
$ L = Rの場合を考えるととりあえず長さ1の区間を$ N個用意するのは必須
上でカバーできない範囲を考えると長さ3の区間が$ N-2個必要
上でカバーできない範囲を、と考えて一つ前の長さを$ xとしたときそれに対して$ 2x+1の長さの区間を用意する
こうすると連続した2区間を使えばどんな長さでも準備できるようになる
クエリに対しては何番目の区間を使えば良いかをひたすらif文で考える
解説によるとSparse Tableの区間そのままに$ 2^xの長さの区間を用意すれば良いらしい