AT_arc068_c [ARC068E] Snuke Line

[problemUrl]: https://atcoder.jp/contests/arc068/tasks/arc068_c すぬけくんは鉄道会社を運営するゲームで遊ぶことにしました。すぬけ鉄道には $ M+1 $ 個の駅があり、 $ 0 $ から $ M $ までの番号がついています。 すぬけ鉄道の列車は駅 $ 0 $ から $ d $ 駅ごとに停車します。 例えば $ d\ =\ 3 $ のとき駅 $ 0 $,駅 $ 3 $,駅 $ 6 $,駅 $ 9 $, $ ... $ に停車します。 すぬけ鉄道が走っている地域には $ N $ 種類の名産品があり、種類 $ i $ の名産品は 駅 $ l_i $,駅 $ l_i+1 $,駅 $ l_i+2 $, $ ... $, 駅 $ r_i $ のいずれかに列車が停車したとき購入することが可能です。 列車が停車する間隔 $ d $ は $ 1,\ 2,\ 3,\ ...,\ M $ の $ M $ 種類が存在しています。 $ M $ 種類の列車それぞれについて、その列車に駅 $ 0 $ で乗車した場合に購入可能な名産品の種類数を求めなさい。 なお、列車から別の列車への乗り換えは許されないものとします。

N/A

N/A

### 制約 - $ 1\ ≦\ N\ ≦\ 3\ ×\ 10^{5} $ - $ 1\ ≦\ M\ ≦\ 10^{5} $ - $ 1\ ≦\ l_i\ ≦\ r_i\ ≦\ M $ ### Sample Explanation 1 \- $ 1 $ 駅ごとに停車する列車に乗った場合、種類 $ 1,2,3 $ の $ 3 $ 種類の名産品を購入することが可能です。 - $ 2 $ 駅ごとに停車する列車に乗った場合、種類 $ 1,2 $ の $ 2 $ 種類の名産品を購入することが可能です。 - $ 3 $ 駅ごとに停車する列車に乗った場合、種類 $ 2,3 $ の $ 2 $ 種類の名産品を購入することが可能です。