E - Many Operations 解説 by Kiri8128
The basic idea is the same as the official editorial , but we have an online solution with \(O(1)\) time per query, keeping the result of all digit in two 30-bit integer. More precisely, we can answer to each query with two integers:
(a) The result after operations \(1,\ 2,\ \cdots, i-1\) when you start with \(0\)
(a) The result after operations \(1,\ 2,\ \cdots, i-1\) when you start with \(m\)
where \(m=2^{30}-1\).
When you answer to the \(i\) th query, consider to split the digits with 1’s and 0’s on the result after the \(i-1\) th query (let \(x\) denote the result). The contribution from \(1\)’s part can be calculated by \((x\ \mathrm{and}\ s_1)\) , while \(0\)’s part by \(((x \ \mathrm{xor}\ m) \ \mathrm{and}\ s_0)\) .
投稿日時:
最終更新: