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