AT_s8pc_2_h Counting 1's

[problemUrl]: https://atcoder.jp/contests/s8pc-2/tasks/s8pc_2_h 長さ$ n $の数列があります。 そして、クエリが$ Q $個与えられます。 各クエリごとに、$ q_i $が与えられます。 ・$ q_i $が$ 1 $のとき、範囲$ l_i≦i＜r_i $の範囲のビットを反転させます。 ・$ q_i $が$ 2 $のとき、範囲$ l_i≦i＜r_i $の範囲に$ 1 $が何個存在するか出力します。 このようなクエリを処理するプログラムを書いてください。 ただし、初期値はすべての位置で$ 0 $とし、一番最初を$ 0 $番目とします。 たとえば、$ n=7,q_i,l_i,r_i $が以下の表のような場合、ビットの状態は以下のようになります。 {$ q_i,l_i,r_i $} 0 0 0 0 0 0 0 出力値 {1,2,5} 0 0 1 1 1 0 0 - {1,4,7} 0 0 1 1 0 1 1 - {2,1,6} 0 0 1 1 0 1 1 3 {1,0,4} 1 1 0 0 0 1 1 - {2,3,7} 1 1 0 0 0 1 1 2 {1,2,6} 1 1 1 1 1 0 1 - {2,0,7} 1 1 1 1 1 0 1 6よって、出力は以下のようになります。 ``` 3 2 6 ```

入力は以下の形式で標準入力から与えられる。 > $ n $ $ Q $ $ q_1 $ $ l_1 $ $ r_1 $ $ : $ $ : $ $ : $ $ q_Q $ $ l_Q $ $ r_Q $ - $ 1 $ 行目には, 数列の長さ$ n $ とクエリの数$ Q $が空白区切りで与えられます。 - $ 2 $ 行目から$ Q+1 $行目にかけて、$ q_i,l_i,r_i $が空白区切りで与えられます。 - $ q_i $はクエリの種類、$ l_i,r_i $はそれぞれ左端、右端の位置です。 - ただし、求める(または反転させる)範囲は右端-1の位置までなので注意すること。

出力は以下の形式で標準出力に従うこと。 - 各出力クエリごとに、$ l_i≦ $(位置)$ ＜r_i $の範囲の$ 1 $の個数を出力してください。 - 各クエリごとに、改行を忘れないこと。

### 制約 - $ 1≦n,Q≦100,000 $ - $ 0≦l_i＜r_i≦n $ - $ 1≦q_i≦2 $ ### 小課題 小課題 $ 1 $ \[ $ 4 $ 点 \] - $ 1≦n,Q≦1,000 $ を満たす。 小課題 $ 2 $ \[ $ 12 $ 点 \] - 出力クエリの数は$ 1,000 $個以内である。 小課題 $ 3 $ \[ $ 36 $ 点 \] - 出力クエリの$ l_i,r_i $は、それぞれ$ 0,n $である。 小課題 $ 4 $ \[ $ 48 $ 点 \] - 追加の制約はない。 ### Sample Explanation 1 数列の値は、以下のように変化します。 {$ q_i,l_i,r_i $} 0 0 0 0 0 0 0 0 出力値 {1,3,7} 0 0 0 1 1 1 1 0 - {2,2,5} 0 0 0 1 1 1 1 0 2 {1,2,4} 0 0 1 0 1 1 1 0 - {2,1,6} 0 0 1 0 1 1 1 0 3 ### Sample Explanation 2 数列の値は以下のように変化します。 {$ q_i,l_i,r_i $} 0 0 0 0 0 出力値 {1,0,3} 1 1 1 0 0 - {1,2,5} 1 1 0 1 1 - {2,1,4} 1 1 0 1 1 2