Codeforces Global Round 2：D - Frets On Fire
問題
解法
まず S をソートしておき，重複しているものは取り除いてよい．
ここで，各クエリで与えられる区間の「位置」は答えに影響を与えず，「長さ」が影響を与える．なぜならば，区間が [l, r] としたら，その区間にあった数全てから l を引けば，区間を [1, r - l + 1] に移動したものと同じと考えることが出来るから．
次に，Fret を 0, 1, 2, ... と増やしていったとき各 S がどこまで Unique な数字を出してくるかを考える．前計算でソートしたので S_(i + 1) > S_i であることに注意すると，区間 [0, S_(i + 1) - S_i] で S_i は Unique な数字を出す．なぜならば，S_i は S_i, S_i + 1, S_i + 2, .. と変化していくにつれていつか S_(i + 1) の最初と重なるから．初めて重なる数字より前が Unique な数字となる．ここで，S_N は無限に Unique な数字を出す．これで各 S について Unique な区間の長さが求まった．
最後に，各クエリの区間の長さ (L とする) と上で求めた各 S について Unique な数字を出す区間の長さを比較する．もし L >= S_i であれば S_i が出す Unique な数字は S_(i + 1) - S_i となる．L < S_i であれば L となる．これは，S_(i + 1) - S_i の値をソートしておくことで，どの S_(i + 1) - S_i が全て答えに加算され，それら以外は L が加算されると二分探索を用いて求めることが出来る．実装では，S_(i + 1) - S_i の値をソートした後累積和を取っておくことで，答えに加算していく段階を O(1) で処理することが出来る．O(NlogN + QlogN)．
解答
