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$.