競技プログラミング用 知識集積所
ABC444E - Sparse Range
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
条件を満たす区間数を求める問題で、単調性が成り立つなら尺取法の出番。
区間[l,r)での要素の一覧をset※等の何らかの方法で保持していれば、二分探索で「r-1番目の要素の±d以内に他の値があるか？」はすぐに確認ができる。
そこさえ正しく対処できれば、あとは尺取法の典型問題。
区間[l,r)での要素の一覧をset※等の何らかの方法で保持していれば、二分探索で「r-1番目の要素の±d以内に他の値があるか？」はすぐに確認ができる。
そこさえ正しく対処できれば、あとは尺取法の典型問題。
解答例
注意点
long long型を使う。
値がそもそも全部バラバラな場合に、答えがint型に収まらない。
