P11016 XOR Pairs

Every day, CT only hums the blues in London and wanders around in front of the school leaders. This lazy and carefree life makes him very down, so he decides to turn over a new leaf and study mathematics.

CT is working on a math problem. CT has a sequence $a$ of length $n$. Now $q$ operations are given. For each operation: - Change $a_x$ to $y$. - After the modification, find the number of valid ordered pairs in the array. **Note:** For a pair $(a_i, a_j)$ with $i < j$ that satisfies $a_i \oplus a_j > \max\{a_i, a_j\}$, we call it a valid pair. Here $\oplus$ denotes bitwise XOR, and $\max\{x, y\}$ denotes the larger one of $x$ and $y$.

The first line contains two integers $n, q$. The second line contains $n$ integers, representing the sequence $a$. The next $q$ lines each contain two integers $x, y$, representing an operation that changes $a_x$ to $y$.

For each operation: Output one integer representing the required answer.

#### Constraints For all testdata, it is guaranteed that $1 \le n \le 10^6$, $1 \le q \le 10^5$, $1 \le a_i \le 10^6$, $1 \le x \le n$, $1 \le y \le 10^6$. |$\text{Subtask}$|$n\leq$|$q\leq$|Score| Special Properties | |:-:|:-:|:-:|:-:|:-:| |$0$|$10^2$|$10^2$|$13$|None| |$1$|$10^6$|$10^5$|$87$|None| Translated by ChatGPT 5