Classical Data Structure Problem
题目描述
有一个长度为 2m 的整数数组 A=[a0,a1,…,a2m−1],初始所有元素均为 0。另有一个整数变量 x,初始 x=0。
对每个 i=1,2,…,n,给出两个整数 pi,qi。请依次执行:
- 令 p′=(pi+x)mod2m、q′=(qi+x)mod2m。
- 令 l=min(p′,q′)、r=max(p′,q′)。
- 对 j=l,l+1,…,r 依次执行:先将 aj 增加 i,再将 x 增加此时的 aj。
求全部操作结束后的 xmod230。本轮区间端点在第1—2步固定;两端均包含,数组下标从0开始。
输入格式
第一行包含两个整数 n,m(1≤n≤500000,1≤m≤30)。
接下来 n 行,第 i 行包含两个整数 pi,qi(0≤pi,qi<2m)。输入没有测试用例数 T。
输出格式
输出一个整数,表示最终的 xmod230。
样例输入 1
5 2
2 1
1 3
3 2
1 0
0 2
样例输出 1
87
样例说明
初始 A=[0,0,0,0],x=0。
- i=1:l=1,r=2,操作后 A=[0,1,1,0],x=2。
- i=2:l=1,r=3,操作后 A=[0,3,3,2],x=10。
- i=3:l=0,r=1,操作后 A=[3,6,3,2],x=19。
- i=4:l=0,r=3,操作后 A=[7,10,7,6],x=49。
- i=5:l=1,r=3,操作后 A=[7,15,12,11],x=87。