Fişierul intrare/ieşire: | bitwiseparty.in, bitwiseparty.out | Sursă | IIOT 2021-22 Runda 3 |
Autor | Stefan Dascalescu | Adăugată de | Stefan Dascalescu •stefdascalescu |
Timp execuţie pe test | 1.25 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bitwise Party
The new year has come and just like all the competitive programmers, our hero Stefan received an array with positive integers as a Christmas present as well! Now he wants to explore the array and to find new interesting properties as he always likes doing.
For this year, he wants to find out the maximum number of values we can take from the array such that both the bitwise AND and the bitwise XOR are different from 0.
Since this is too easy for him, he also modifies his array and wants you to answer to the same question after each update.
Date de intrare
The input file bitwiseparty.in contains n, the number of integers from the array and q, the number of queries.
The next line contains n integers, representing the numbers from Stefan's array.
The next q lines contain the queries. Each query is represented by two integers, pos and val, representing that on the position pos, we will change its value to val.
Date de ieşire
The output file bitwiseparty.out will contain q+1 lines. On the first line you will print the answer before any updates, and on the next q lines you will print the answer after each update.
Restricţii
- 1 ≤ n, q ≤ 2 * 10^5
- 1 ≤ v[i], val < 2^20
- For tests worth 10 points, 1 ≤ v[i], val ≤ 2.
- For tests worth 20 more points, 1 ≤ n, q, val, v_i < 2^7.
- For tests worth 20 more points, 1 ≤ n, q, val, v_i < 2^10.
Exemplu
bitwiseparty.in | bitwiseparty.out |
---|---|
5 8 3 2 4 1 5 1 1 2 3 3 3 4 2 3 6 4 5 5 2 1 6 | 3 3 4 5 4 3 4 3 4 |