H - Counting 1's Editorial /

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

長さ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 点 ]

  • 追加の制約はない。

入力例1

8 4
1 3 7
2 2 5
1 2 4
2 1 6

出力例1

2
3

数列の値は、以下のように変化します。

{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

入力例2

5 3
1 0 3
1 2 5
2 1 4

出力例2

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

入力例3

7 7
2 3 4
1 4 6
2 1 5
1 0 7
1 2 5
2 0 7
1 2 3

出力例3

0
1
4

問題文担当者:square1001