3589. [NOI Online 2021 1st] 岛屿探险

【题目描述】

凇睦是一个喜欢探险的女孩子，这天她到一片海域上来探险了。

在这片海域上一共有n座岛屿排成一排，标号为1,2,3,...,n。每座岛屿有两个权值，分别为劳累度ai 和有趣度 bi 。

对于一座劳累度为a，有趣度为b的小岛，如果这个小岛满足(a⊕c) ≤ min(b,d)，凇睦到这座岛探险就会感到开心，其中c表示凇睦到岛上去之前就有的劳累度（称作初始劳累度），同理d代表凇睦的初始有趣度。⊕表示二进制异或（即二进制表示下不进位的加法）。

为了玩的更尽兴，凇睦会向你询问q次，每次给出一个区间[li ,ri ] 和两个数 ci ,di ，你需要告诉凇睦若她的初始劳累度为ci ，初始有趣度为di ，则有多少个标号在[li ,ri] 这个区间内的岛屿能使凇睦探险时感到开心。

【输入格式】

第一行两个正整数n,q 分别表示岛屿的数量和询问的数量。

接下来 n 行，每行两个整数ai ,bi 分别表示第 i 座岛屿的劳累度和有趣度。

接下来 q 行，每行四个正整数li ,ri ,ci ,di 分别表示区间左端点，区间右端点，初始劳累度与初始有趣度。

【输出格式】

输出一共 q 行，每行一个整数对应一个询问的答案。

【样例1输入】

4 2
1 1
4 2
5 1
2 7
1 4 6 5
2 4 3 3

【样例1输出】

2
1

【样例1说明】

第一次询问中，岛屿 2 与岛屿 4 能使凇睦探险时感到开心。而在第二次询问中，只有岛屿 4 能使凇睦探险时感到开心。

【样例2输入】

20 10
215 144
2 110
174 132
214 142
116 108
155 192
236 208
216 214
99 220
 236 118
190 81
230 131
10 238
189 198
183 13
45 193
14 234
208 192
126 19
49 38
7 14 251 184
2 18 89 76
11 15 49 196
8 11 83 139
10 15 119 239
9 16 148 120
11 17 225 34
15 16 3 46
14 15 86 227
7 18 252 103

【样例2输出】

7
2
2
2
1
3
1
1
0
7

【数据规模与约定】

对于所有测试点，1 ≤ n,q ≤ 10^5 ，1 ≤ li ≤ ri ≤ n，1 ≤ ai ,bi ,ci ,di ≤ 2^24 − 1。