Fişierul intrare/ieşire:bitwiseparty.in, bitwiseparty.outSursăIIOT 2021-22 Runda 3
AutorStefan DascalescuAdăugată destefdascalescuStefan Dascalescu stefdascalescu
Timp execuţie pe test2.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inbitwiseparty.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?