P5105 Dynamic Quicksort Not Forced to Be Online

Xiyue recently learned quicksort, but she soon thought: if we need to sort dynamically, what should we do?

To study this problem, Xiyue proposed a very simple question. Xiyue wants to maintain a multiset $S$ that allows duplicates, supporting: * Insert $[L, R]$, i.e., insert $L, L + 1 ... , R$, these $R - L + 1$ numbers. * Query $Sort(S)$. --- The definition of $Sort(S)$ is: We sort the elements in $S$ from small to large **using quicksort**, denoted as $a_1, a_2 ... a_n$. Then, $Sort(S) = \bigoplus \limits_{i = 2}^n (a_i^2 - a_{i - 1}^2)$, where $\bigoplus$ denotes XOR. For the definition of XOR, please consult Baidu.

The first line contains an integer $q$. The next $q$ lines are either $1\;l\;r$, meaning insert $[l, r]$, or $2$, meaning one query.

For each query, output one line with one answer.

Explanation for Sample 1: $S$ contains only one number, so return $0$. --- Constraints: For the $30$ points testdata, $q \leqslant 100$. For the $50$ points testdata, $q \leqslant 5 * 10^4$. For the other $20$ points testdata, $L = R$. For the $100$ points testdata, $q \leqslant 3 * 10^5$, $1 \leqslant L \leqslant R \leqslant 10^9$. The testdata is guaranteed to have gradients. It may be slightly sensitive to constants, so please optimize your constants as much as possible. Translated by ChatGPT 5