CF1515H Phoenix and Bits

Phoenix loves playing with bits — specifically, by using the bitwise operations AND, OR, and XOR. He has $ n $ integers $ a_1, a_2, \dots, a_n $ , and will perform $ q $ of the following queries: 1. replace all numbers $ a_i $ where $ l \le a_i \le r $ with $ a_i $ AND $ x $ ; 2. replace all numbers $ a_i $ where $ l \le a_i \le r $ with $ a_i $ OR $ x $ ; 3. replace all numbers $ a_i $ where $ l \le a_i \le r $ with $ a_i $ XOR $ x $ ; 4. output how many distinct integers $ a_i $ where $ l \le a_i \le r $ . For each query, Phoenix is given $ l $ , $ r $ , and $ x $ . Note that he is considering the values of the numbers, not their indices.

N/A

N/A

In the first example: - For the first query, $ 2 $ is replaced by $ 2 $ AND $ 2 = 2 $ and $ 3 $ is replaced with $ 3 $ AND $ 2 = 2 $ . The set of numbers is $ \{1, 2, 4, 5\} $ . - For the second query, there are $ 3 $ distinct numbers between $ 2 $ and $ 5 $ : $ 2 $ , $ 4 $ , and $ 5 $ . - For the third query, $ 2 $ is replaced by $ 2 $ XOR $ 3 = 1 $ , $ 4 $ is replaced by $ 4 $ XOR $ 3 = 7 $ , and $ 5 $ is replaced by $ 5 $ XOR $ 3 = 6 $ . The set of numbers is $ \{1, 6, 7\} $ . - For the fourth query, there are $ 2 $ distinct numbers between $ 1 $ and $ 6 $ : $ 1 $ and $ 6 $ . - For the fifth query, $ 1 $ is replaced by $ 1 $ OR $ 8 = 9 $ . The set of numbers is $ \{6, 7, 9\} $ . - For the sixth query, there is one distinct number between $ 8 $ and $ 10 $ : $ 9 $ .