#P4571. [Scoi2016]美味

    ID: 3674 传统题 2000ms 256MiB 尝试: 1170 已通过: 564 难度: 7 上传者: 标签>CF2200提高+/省选-按位贪心可持久化线段树路径复制前缀版本作差

[Scoi2016]美味

题目描述

一家餐厅有 nn 道菜,编号 1…n1 \dots n,大家对第 ii 道菜的评价值为 ai (1≤i≤n)a_i\ (1 \leq i \leq n)。

有 mm 位顾客,第 ii 位顾客的期望值为 bib_i,而他的偏好值为 xix_i。
因此,第 ii 位顾客认为第 jj 道菜的美味度为 bi xor⁡ (aj+xi)b_i\ \operatorname{xor}\ (a_j+x_i),其中 xor⁡\operatorname{xor} 表示异或运算。

第 ii 位顾客希望从这些菜中挑出他认为最美味的菜,即美味值最大的菜,但由于价格等因素,他只能从第 lil_i 道到第 rir_i 道中选择。请你帮助他们找出最美味的菜。

输入格式

第 11 行,两个整数,n,mn,m,表示菜品数和顾客数。
第 22 行,nn 个整数,a1,a2,…,ana_1,a_2,\dots,a_n,表示每道菜的评价值。
第 33 至 m+2m+2 行,每行 44 个整数,b,x,l,rb,x,l,r,表示该位顾客的期望值,偏好值,和可以选择菜品区间。

输出格式

输出 mm 行,每行 11 个整数,ymaxymax,表示该位顾客选择的最美味的菜的美味值。

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

数据规模与约定

对于 100%100\% 的数据,1≤n≤2×1051 \leq n \leq 2 \times 10^5,0≤ai,bi,xi<1050 \leq a_i,b_i,x_i<10^5,1≤li≤ri≤n (1≤i≤m)1 \leq l_i \leq r_i \leq n\ (1 \leq i \leq m);1≤m≤1051 \leq m \leq 10^5。