28204번 - Classical Data Structure Problem 다국어

You have an integer array $A = [a_0, a_1, \ldots, a_{2^m-1}]$ of length $2^m$. Initially, the array consists of zeros.

You also have an integer variable $x$. Initially, $x = 0$.

For each $i = 1, 2, \ldots, n$, you are given two integers $p_i$ and $q_i$, and you have to perform the following steps:

• Let $p' = (p_i + x) \bmod 2^m$ and $q' = (q_i + x) \bmod 2^m$.
• Let $l = \min(p', q')$ and $r = \max(p', q')$.
• For each $j = l, l+1, \ldots, r$, increase $a_j$ by $i$, then increase $x$ by $a_j$.

Find the value of $x \bmod 2^{30}$ at the end of this process.

The first line contains two integers $n$ and $m$ ($1 \le n \le 500\,000$; $1 \le m \le 30$).

The $i$-th of the following $n$ lines contains two integers $p_i$ and $q_i$ ($0 \le p_i, q_i < 2^m$).

Print the value of $x \bmod 2^{30}$.

In the example test, initially, $A = [0, 0, 0, 0]$ and $x = 0$. Then:

• For $i = 1$, we have $l = 1$ and $r = 2$. Then, $A = [0, 1, 1, 0]$ and $x = 2$.
• For $i = 2$, we have $l = 1$ and $r = 3$. Then, $A = [0, 3, 3, 2]$ and $x = 10$.
• For $i = 3$, we have $l = 0$ and $r = 1$. Then, $A = [3, 6, 3, 2]$ and $x = 19$.
• For $i = 4$, we have $l = 0$ and $r = 3$. Then, $A = [7, 10, 7, 6]$ and $x = 49$.
• For $i = 5$, we have $l = 1$ and $r = 3$. Then, $A = [7, 15, 12, 11]$ and $x = 87$.