以下では、左右一列に並んだ \(N\) マスのうち、左から \(i\) 番目のマスをマス \(i\) とします。
また、便宜上、\(N\) マスの左右に \(1\) マスずつ（マス \(0\), マス \((N+1)\) ）を付け加え、それらはつねに白く塗られているものとします。

単純な解法として、問題文の指示通り、マスの色を反転し、区間の個数を数えるという方法がありますが、これは愚直に実装すると、\(O(NQ)\) あるいは \(O(N^2Q)\) となり、実行時間制限をみたすことは厳しいです。よって、より高速にこの問題を解く方法を考える必要があります。

ある時点において、\(0\leq i\leq N\) のうち、マス \(i\) とマス \((i+1)\) の色が異なるような \(i\) の個数を \(k\) として、そのような \(i\) を \(i_1,i_2,\ldots,i_k\) とします。 このとき、マス目は次のような状態です。

• \(0\leq j\leq i_1\) について、マス \(j\) は白く塗られている。
• \(i_1+1\leq j\leq i_2\) について、マス \(j\) は黒く塗られている。
• \(i_2+1\leq j\leq i_3\) について、マス \(j\) は白く塗られている。
• \(\cdots\)
• \(i_{k-1}+1\leq j\leq i_k\) について、マス \(j\) は黒く塗られている。
• \(i_k+1\leq j\leq N+1\) について、マス \(j\) は白く塗られている。

よって、黒く塗られたマスが連続している区間はちょうど \(\frac{k}{2}\) です。ここで、マス \(0, (N+1)\) はつねに白く塗られていることから、\(k\) は必ず偶数であることに注意してください。

このことから、各クエリを処理した後のマス \(i\) とマス \((i+1)\) の色が異なるような \(i\) の個数が分かれば十分です。 それぞれの時点において、マス \(i\) とマス \((i+1)\) の色が異なっているかどうか管理する事を考えます。
最初、すべてのマスは白く塗られているので、すべての \(0\leq i\leq N\) について、マス \(i\) とマス \((i+1)\) の色は等しいです。 マス \(X\) \((1\leq X\leq N)\) の色を反転した時、起きる変化は次の \(2\) つです。

• \(i=X-1\) について、マス \(i\) とマス \((i+1)\) の色が等しかったならば異なるようになる。異なっていたならば、等しくなる。
• \(i=X\) について、マス \(i\) とマス \((i+1)\) の色が等しかったならば異なるようになる。異なっていたならば、等しくなる。

よって、\(1\) 個のクエリによって、各クエリを処理した後のマス \(i\) とマス \((i+1)\) の色が異なるような \(i\) の個数は、 \(2\) 増える、\(2\) 減る、変わらないのいずれかであり、どれであるかは反転前の状態において、\(i=X-1,X\) それぞれについてマス \(i\) とマス \((i+1)\) の色が異なっていたかによってのみ決まります。よって、それぞれの時点において、各 \(0\leq i\leq N について、\)マス \(i\) とマス \((i+1)\) の色が異なっているかを管理する配列、および異なっている \(i\) の個数を管理する変数があれば各クエリについて \(O(1)\) （定数時間）で答えを求めることができます。
このとき、時間計算量は全体で \(O(Q)\) であり、十分高速です。
よって、この問題を解くことができました。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n,q,x,s=0;
	cin >> n >> q;

	vector<int> a(n+1);
	for(int i=0;i<q;i++){
		cin >> x;
		s += (1-a[x-1])-a[x-1];
		s += (1-a[x])-a[x];
		a[x-1] = 1-a[x-1];
		a[x] = 1-a[x];
		cout << (s/2) << endl;
	}

	return 0;
}