一度のスイッチ切り替えを、照明 \(L_i,L_i+1,\dots,R_i\) までのスイッチの切り替え回数に \(1\) 加算する行為であると捉えます。
すると、各照明について、切り替え回数が奇数 ( \(2\) で割った余りが \(1\) である ) である時、またその時に限り、最終的にその照明が点灯しています。

すると、数列のうちある区間 \([L_i,R_i]\) に \(1\) を加算するという行為をまとめて高速に処理できればよいということになります。
そこで、 imos法 と呼ばれる方法を用います。この方法を今回の問題に沿った形で説明します。

• 「 \(A_{L_i},A_{L_i+1},\dots,A_{R_i}\) に \(W_i\) を加算する」というクエリが沢山あり、これらをまとめて処理したい。
• まず、ひとつの加算を以下の形に変換する。
  • \(A_{L_i}\) に \(W_i\) 加算する。
  • \(A_{R_i+1}\) から \(W_i\) 減算する。
• 全ての加算の処理を終えた後、以下の通りに累積和を取る処理を行う。
  • \(A_{i+1}\) に \(A_i\) を加算することを、 \(i\) の昇順に繰り返す。

このようにすることで、変換した後の加算が累積和を取った後に区間加算に対応していることがわかります。

理解の助けの為、具体例を示します。

• \(A_2,A_3,A_4\) に \(1\) を加算したいとする。
  • \(A_2\) に \(1\) 加算、 \(A_5\) から \(1\) 減算と言い換えられる。この時点で \(A=(0,1,0,0,-1,0,\dots)\) です。
• \(A_3,A_4,A_5\) に \(10\) を加算したいとする。
  • \(A_3\) に \(10\) 加算、 \(A_6\) から \(10\) 減算と言い換えられる。この時点で \(A=(0,1,10,0,-1,-10,\dots)\) です。
• これで全ての加算が完了したとする。
  • \(A\) の累積和を取る。 \(A=(0,1,11,11,10,0,\dots)\) となり、所望の加算が実現していることが分かる。

こうすることで、各照明のスイッチを切り替えた回数が全ての照明に対して求まり、この問題を解くことができます。
時間計算量は \(O(N+M)\) です。

Bonus! \(N \le 10^{18}\) という制約でもこの問題を解くことができます。この解説の方針を拡張しても対応可能な他、こちらの AI 解説がこの制約に対応可能な方針です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> s(N+2,0);
  while(M--){
    int L,R;
    cin >> L >> R;
    s[L]++;
    s[R+1]--;
  }
  int res=0;
  for(int i=1;i<=N;i++){
    if(s[i]%2){res++;}
    s[i+1]+=s[i];
  }
  cout << res << "\n";
  return 0;
}