E - Many Operations

[hxrxchang]

https://atcoder.jp/contests/abc261/tasks/abc261_e

問題概要

変数Xがあり、初期値はCである。
以下の3種類の操作がN個ある。

• T=1のとき、X = X and A にする
• T=2のとき、X = X or A にする
• T=3のとき、X= X xor A にする

これを、

• 操作1
• 操作1, 操作2
• 操作1, 操作2, 操作3
• 操作1, 操作2, 操作3, 操作4..., 操作N

と繰り返し行い、各タイミングでのXの状態を出力せよ。

解き方

初期状態で

• 全部bitが立った整数 u
• 全部bitが立っていない整数 d

を用意して、n回の各操作を行っていく。
これはbit演算はbit毎に独立なので、初期1だったbitと初期0だったbitが各操作でどうなるかが分かれば、xの各bitがどうなるかも分かるということ。
CもAも最大30bitなので、各操作後に全bitがどうなっているか調べることができる。
全体の計算量は 10 ** 5 * 30になる。

func solve() {
	in := getInts()
	n, c := in[0], in[1]

	u := (1 << 30) - 1
	d := 0
	x := c
	for i := 0; i < n; i++ {
		in := getInts()
		t, a := in[0], in[1]

		if t == 1 {
			u &= a
			d &= a
		} else if t == 2 {
			u |= a
			d |= a
		} else if t == 3 {
			u ^= a
			d ^= a
		}

		nx := 0
		for j := 0; j < 30; j++ {
			if (x & (1 << j)) != 0 {
				nx += (u & (1 << j))
			} else {
				nx += (d & (1 << j))
			}
		}
		x = nx
		fmt.Println(x)
	}
}

https://atcoder.jp/contests/abc261/submissions/60639965