【ABC408】C問題 - Not All Covered 考察から実装(c++)まで

AtCoderBeginnerContest408の解説＆感想です。
コンテストリンク

問題一覧

• 【ABC408】A問題 - Timeout　考察から実装(c++)まで
• 【ABC408】B問題 - Compression　考察から実装(c++)まで
• 【ABC408】C問題 - Not All Covered　考察から実装(c++)まで <- イマココ
• 【ABC408】D問題 - Flip to Gather　考察から実装(c++)まで
• 【ABC408】E問題 - Minimum OR Path　考察から実装(c++)まで
• 【ABC408】F問題 - Athletic　考察から実装(c++)まで

C問題 - Not All Covered

問題リンク

問題概要

$1$から$N$まで番号付けられた$N$個の城壁と、$M$個の砲台がある。砲台$i$は城壁$L_i$から$R_i$を守っている。
どの砲台にも守られていない城壁ができるまでには、最小でいくつの砲台を壊す必要があるか？

制約

• $ 1 \le N \le 10^6 $
• $ 1 \le M \le 2 \times 10^5 $
• $ 1 \le L_i \le R_i \le N $

考察

愚直解はかなり素直に考えればよくて、各城壁についてそこを守っている砲台の数を出して、その中の最小値を求めればいい。
「区間$(L_i, R_i)$全てを+1する」という処理を$M$回やればいいけど、愚直にやると$O(NM)$となり間に合わない。これをどう高速化しますかという問題。

「区間に定数を足す」というのは典型で、imos法で高速化できる。
計算量は$O(N+M)$

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<long long>;
int main(void){
    //入力
    ll N,M;
    cin>>N>>M;
    
    vll imos(N+1,0);
    for(int i=0;i<M;i++){
        ll L,R;
        cin>>L>>R;
        //L-1番目 ~ R-1番目に+1したい
        imos[L-1]++;
        imos[R]--;
    }
    for(int i=0;i<N;i++) imos[i+1] += imos[i];
    
    //0番目からN-1番目の中で、一番小さいところを表示
    cout<<*min_element(imos.begin(), imos.end()-1)<<endl;
    return 0;
}