#PQJ214x2795. QOJ 214_2795

    ID: 2779 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SCOI 2016二分答案

QOJ 214_2795

美味 一家餐厅有n 道菜,编号1. . . n,大家对第i 道菜的评价值为ai(1 ≤i ≤n)。 有m 位顾客,第i 位顾客的期望值为bi,而他的偏好值为xi。 因此,第i 位顾客认为第j 道菜的美味度为bi XOR (aj + xi),XOR 表示异或运算。 第i 位顾客希望从这些菜中挑出他认为最美味的菜,即美味值最大的菜,但由于价格等因素,他只能从第li 道到第ri 道中选择。 请你帮助他们找出最美味的菜。 输入 第1 行,两个整数,n, m,表示菜品数和顾客数。 第2 行,n 个整数,a1, a2, · · · , an,表示每道菜的评价值。 第3 至m+2 行,每行4 个整数,b, x, l, r,表示该位顾客的期望值,偏好值,和可以选择菜品区间。 输出 输出m 行,每行1 个整数,ymax,表示该位顾客选择的最美味的菜的美味值。 样例 样例输入 样例输出 4 4 1 2 3 4 1 4 1 4 2 3 2 3 3 2 3 3 4 1 2 4 9 7 6 7 数据范围 其中,1 ≤n ≤2 × 105, 0 ≤ai, bi, xi < 105, 1 ≤li ≤ri ≤n(1 ≤i ≤m) 对于30% 的数据,1 ≤m ≤103 对于100% 的数据,1 ≤m ≤105 3