题目大意
给出一个序列AAA进行qqq次提问,每次会提问一个区间[l,r][l,r][l,r],求解区间A[l,r]A_{[l,r]}A[l,r] 按照给定规则计算的最大值与最小值为多少。
解题思路
设lowbit(x)lowbit(x)lowbit(x)为获取字符xxx的二进制最低位1码权，可得等价公式
1. lowbit(ai)=lowbit(aj)lowbit(a_i) = lowbit(a_j)lowbit(ai )=lowbit(aj ) : answer=ai∣ajanswer = a_i | a_janswer=ai ∣aj
2. lowbit(ai)≠lowbit(aj)lowbit(a_i) \neq lowbit(a_j)lowbit(ai )=lowbit(aj ) : answer=min(lowbit(ai),lowbit(aj))answer = min(lowbit(a_i),lowbit(a_j))answer=min(lowbit(ai ),lowbit(aj ))
一个区间当中，我们根据不同数字的lowbit(x)lowbit(x)lowbit(x)作为划分种类的阶层，那么假设存在kkk的阶层，且lowbit(x)lowbit(x)lowbit(x)的最小值为zzz，设该阶层的序列为BBB,其中每个元素BiB_iBi 都满足lowbit(Bi)=zlowbit(B_i) = zlowbit(Bi )=z，那么对于每个问答的解题过程如下:
1. k=1k = 1k=1 : max=min=al∣al+1∣…armax = min = a_l | a_{l+1} | \dots a_{r}max=min=al ∣al+1 ∣…ar
2. k≠1k \neq 1k=1 : $answer_max = max(z | A^{B-1}_B) $ , answer_min=zanswer\_min = zanswer_min=z。
注:ABB−1A^{B-1}_BABB−1 即为从B序列当中拿取B−1B-1B−1个数字进行全排列。
时间复杂度
O(n×q×)O(n \times q \times )O(n×q×)
代码示范
