ABC127 C - Prison - ツバサの備忘録

解法

$sum[i] = i$ 枚目のカードを用いて通ることができるゲートの個数

とすると、 $sum[i] = M$ となるような $i$ の個数が答えになります。
ということで、各ゲートについて与えられる区間 $[L_{j},R_{j}]$ について、 $sum[L_{j}],sum[L_{j}+1],...sum[R_{j}]$ に1を追加する、という操作をしてあげれば、 $i$ 枚目のカードを用いて通ることができるゲートの個数を求めることができます。
単純に加算していくと間に合わないので、いもす法を用います。
$sum[L_{j}]$ に1を加算し、 $sum[R_{j}+1]$ から1を減らしてあげて、 $sum[1]$ から順番に累積和を取っていくと、 $O(N)$ で求めることができます。