中文
日本語
English
| P8009[NOI Online 2021] 岛屿探险 | ||
|
Description
凇睦是一个喜欢探险的女孩子，这天她到一片海域上来探险了。
在这片海域上一共有 \(n\) 座岛屿排成一排，标号为 \(1,2,3,\cdots,n\) 。每座岛屿有两个权值，分别为劳累度 \(a_i\) 和有趣度 \(b_i\) 。
对于一座劳累度为 \(a\) ，有趣度为 \(b\) 的小岛，如果这个小岛满足 \((a\oplus c)\leq min(b,d)\) ，凇睦到这座岛探险就会感到开心，其中 \(c\) 表示凇睦到岛上去之前就有的劳累度（称作初始劳累度），同理 \(d\) 代表凇睦的初始有趣度。 \(\oplus\) 表示二进制异或（即二进制表示下不进位的加法）。
为了玩的更尽兴，凇睦会向你询问 \(q\) 次，每次给出一个区间 \([l_i,r_i]\) 和两个数 \(c_i,d_i\) ，你需要告诉凇睦若她的初始劳累度为 \(c_i\) ，初始有趣度为 \(d_i\) ，则有多少个标号在 \([l_i,r_i]\) 这个区间内的岛屿能使凇睦探险时感到开心。
Input Format
第一行两个正整数 \(n,q\) 分别表示岛屿的数量和询问的数量。
接下来 \(n\) 行，每行两个整数 \(a_i, b_i\) 分别表示第 \(i\) 座岛屿的劳累度和有趣度。
接下来 \(q\) 行，每行四个正整数 \(l_i, r_i, c_i, d_i\) 分别表示区间左端点，区间右端点，初始劳累度与初始有趣度。
Output Format
输出一共 \(q\) 行，每行一个整数对应一个询问的答案。
Sample Input 1
4 2
1 1
4 2
5 1
2 7
1 4 6 5
2 4 3 3
Sample Output 1
2
1
Sample Input 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
Sample Output 2
7
2
2
2
1
3
1
1
0
7
Hint
样例1解释
第一次询问中，岛屿 \(2\) 与岛屿 \(4\) 能使凇睦探险时感到开心。而在第二次询问中，只有岛屿 \(4\) 能使凇睦探险时感到开心。
数据范围
对于所有测试点， \(1\leq n,q\leq 10^5\) ， \(1\leq l_i\leq r_i\leq n\) ， \(1\leq a_i,b_i,c_i,d_i\leq 2^{24}-1\) 。
| 测试点 | \(n,q\leq\) | 特殊性质 |
|---|---|---|
| $1\sim 2$ | $5000$ | 无 |
| $3\sim 4$ | $10^4$ | 无 |
| $5\sim 7$ | $10^5$ | \(\max\{d_i\}\leq\min\{b_i\}\) |
| $8\sim 11$ | $10^5$ | \(\min\{d_i\}\geq\max\{b_i\}\) |
| $12\sim 13$ | $10^5$ | \(l_i=1\) ， \(r_i=n\) |
| $14\sim 16$ | $7\times 10^4$ | 无 |
| $17\sim 20$ | $10^5$ | 无 |
update 2021.3.28：每组时限已从2s加到4s