2 - たのしい画像収集 (Collecting Images is Fun) 解説 /

実行時間制限: 5 sec / メモリ制限: 256 MiB

配点 : 100 点

問題文

JOI 君は画像をたくさん集めることが大好きで,多くの画像を持っている.最近になって JOI 君は,画像を集めすぎてしまったせいでハードディスクの容量が不足気味になっていることに気がついた.新しくハードディスクを購入するお金はないが,JOI 君にとって持っている画像を削除することはこの上ない苦痛であるため,画像をうまく圧縮して容量を削減することにした.

画像は縦 2^{N} 行,横 2^{N} 列の正方形状に並んだ合計 2^{N} \times 2^{N} 個の画素で表される.それぞれの画素は白か黒のいずれかである.

このような画像を JOI 君は次の方法で圧縮することにした.

  • 画像内の画素がすべて同じ色ならば,その色だけを記録する.このとき圧縮後のデータの大きさは 1 である.
  • そうでなければ,画像を 4 つのより小さな画像に分ける.画像が縦 2^{k} 行,横 2^{k} 列であるとすると,縦と横それぞれ中心で画像を分割し,縦 2^{k - 1} 行,横 2^{k - 1} 列の画像 4 つを得る.これら 4 つの小さくなった画像を同じ方法で圧縮する.このとき圧縮後のデータの大きさは,4 つの小さい画像の圧縮後のデータの大きさの和に,さらに 1 を加えたものであるとする.

JOI 君はこの方法で本当に画像が圧縮できるのか不安になったため,さまざまな画像に対して実験をしてみることにした.実験の方法は次のようなものである.

  • まずすべての画素が白であるような画像を用意する.
  • i = 1, \cdot \cdot \cdot , Q について,「T_{i} = 0 ならば上から数えて X_{i} 行目の 2^{N} 個の画素,T_{i} = 1 ならば左から数えて X_{i} 列目の 2^{N} 個の画素の,白黒をそれぞれ反転させる」という操作を行う.すなわち,上から a 行目で左から b 列目にあるカードを (a, b) と書いたとき,各 i について,T_{i} = 0 ならば 1 \leqq b \leqq 2^{N} をみたす画素 (X_{i}, b) に,T_{i} = 1 ならば 1 \leqq a \leqq 2^{N} をみたす画素 (a, X_{i}) に対し,画素が白ならば黒に,黒ならば白に変える操作を行う.
  • 各 i について,i 回目の操作が終わったあとの画像を JOI 君の方法で圧縮したときの,圧縮後のデータの大きさを調べる.

実験では操作をできるだけ多く行うために,圧縮後のデータの大きさを高速に調べる必要がある.

課題

画像の大きさを表す整数 N,操作の回数 Q および Q 回の操作の指示が与えられたとき,それぞれの操作が終わった後の画像を JOI 君の方法で圧縮したときの,圧縮後のデータの大きさを求めるプログラムを作成せよ.

入力

標準入力から以下の入力を読み込め.

  • 1 行目には 2 つの整数 N, Q が空白を区切りとして書かれており,画像が 2^{N} 行 2^{N} 列の大きさであることと,操作を行う回数が Q 回であることを表す.
  • 続く Q 行には操作の指示が書かれている.Q 行のうちの i 行目 (1 \leqq i \leqq Q) には 2 つの整数 T_{i}, X_{i} (0 \leqq T_{i} \leqq 1 かつ 1 \leqq X_{i} \leqq 2^{N}) が空白を区切りとして書かれており,i 回目の操作は T_{i} = 0 なら上から X_{i} 行目,T_{i} = 1 なら左から X_{i} 列目の画素の白黒を全て反転することを表す.

出力

標準出力に Q 行出力せよ.i 行目 (1 \leqq i \leqq Q) には,i 回目の操作が終わった後の画像を JOI 君の方法で圧縮したときの,圧縮後のデータの大きさを表す 1 つの整数を出力せよ.

制約

すべての入力データは以下の条件を満たす.

  • 1 \leqq N \leqq 20.
  • 1 \leqq Q \leqq 2\,000\,000.

小課題

小課題 1 [10 点]

以下の条件を満たす.

  • N \leqq 6.
  • Q \leqq 128.

小課題 2 [20 点]

以下の条件を満たす.

  • N \leqq 10.
  • Q \leqq 2\,048.

小課題 3 [70 点]

  • 追加の制限はない.

入出力例

入力例 1

2 3
0 1
1 2
0 3

出力例 1

13
17
21

この例では,Q = 3 回の操作は以下のように行われる.

初期状態

□□□□
□□□□
□□□□
□□□□

↓

■■■■
□□□□
□□□□
□□□□

↓

■□■■
□■□□
□■□□
□■□□

↓

■□■■
□■□□
■□■■
□■□□

出典

JOI 2012/2013 春季トレーニング合宿 Contest Day1