#P18673. Classical Data Structure Problem

Classical Data Structure Problem

Classical Data Structure Problem

题目描述

有一个长度为 2m2^m 的整数数组 A=[a0,a1,…,a2m−1]A=[a_0,a_1,\ldots,a_{2^m-1}],初始所有元素均为 00。另有一个整数变量 xx,初始 x=0x=0。

对每个 i=1,2,…,ni=1,2,\ldots,n,给出两个整数 pi,qip_i,q_i。请依次执行:

  1. 令 p′=(pi+x) mod 2mp'=(p_i+x)\bmod2^m、q′=(qi+x) mod 2mq'=(q_i+x)\bmod2^m。
  2. 令 l=min⁡(p′,q′)l=\min(p',q')、r=max⁡(p′,q′)r=\max(p',q')。
  3. 对 j=l,l+1,…,rj=l,l+1,\ldots,r 依次执行:先将 aja_j 增加 ii,再将 xx 增加此时的 aja_j。

求全部操作结束后的 x mod 230x\bmod2^{30}。本轮区间端点在第1—2步固定;两端均包含,数组下标从0开始。

输入格式

第一行包含两个整数 n,mn,m(1≤n≤5000001\le n\le500000,1≤m≤301\le m\le30)。

接下来 nn 行,第 ii 行包含两个整数 pi,qip_i,q_i(0≤pi,qi<2m0\le p_i,q_i<2^m)。输入没有测试用例数 TT。

输出格式

输出一个整数,表示最终的 x mod 230x\bmod2^{30}。

样例输入 1

5 2
2 1
1 3
3 2
1 0
0 2

样例输出 1

87

样例说明

初始 A=[0,0,0,0]A=[0,0,0,0],x=0x=0。

  • i=1i=1:l=1,r=2l=1,r=2,操作后 A=[0,1,1,0]A=[0,1,1,0],x=2x=2。
  • i=2i=2:l=1,r=3l=1,r=3,操作后 A=[0,3,3,2]A=[0,3,3,2],x=10x=10。
  • i=3i=3:l=0,r=1l=0,r=1,操作后 A=[3,6,3,2]A=[3,6,3,2],x=19x=19。
  • i=4i=4:l=0,r=3l=0,r=3,操作后 A=[7,10,7,6]A=[7,10,7,6],x=49x=49。
  • i=5i=5:l=1,r=3l=1,r=3,操作后 A=[7,15,12,11]A=[7,15,12,11],x=87x=87。