正经题解｜狒狒食肆

题目大意

给出一个序列$A$进行$q$次提问,每次会提问一个区间$[l,r]$,求解区间$A_{[l,r]}$按照给定规则计算的最大值与最小值为多少。

解题思路

设$lowbit(x)$为获取字符$x$的二进制最低位1码权，可得等价公式

1. $lowbit(a_i) = lowbit(a_j)$ : $answer = a_i | a_j$
2. $lowbit(a_i) \neq lowbit(a_j)$ : $answer = min(lowbit(a_i),lowbit(a_j))$

一个区间当中，我们根据不同数字的$lowbit(x)$作为划分种类的阶层，那么假设存在$k$的阶层，且$lowbit(x)$的最小值为$z$，设该阶层的序列为$B$,其中每个元素$B_i$都满足$lowbit(B_i) = z$，那么对于每个问答的解题过程如下:

1. $k = 1$ : $max = min = a_l | a_{l+1} | \dots a_{r}$
2. $k \neq 1$ : $answer_max = max(z | A^{B-1}_B) $ , $answer\_min = z$。

注:$A^{B-1}_B$即为从B序列当中拿取$B-1$个数字进行全排列。

时间复杂度

$O(n \times q \times )$

代码示范

#include<bits/stdc++.h>
using namespace std;
int n,q,a[100005],b[100005];
int lowbit(int x)
{
    return x & -x;
}
int main()
{
    cin >> n >> q;
    for(int i = 1 ; i <= n ; i ++ )cin >> a[i];
    while(q--)
    {
        int l,r;
        cin >> l >> r ;
        int mi_2 = INT_MAX;
        for(int i = l ; i <= r ; i ++ ){
            mi_2 = min(mi_2,lowbit(a[i]));
        }
        vector<int> ve;
        for(int i = l ; i <= r ; i ++ )
        {
            if(lowbit(a[i]) == mi_2)ve.push_back(i);
        }
        int answer = 0 ;
        if(ve.size() == r - l + 1)
        {
            for(int i = l ; i <= r ; i ++ )answer |= a[i];
            cout << answer << " " << answer << endl;
        }else{
            for(auto i : ve)
            {
                int temp = mi_2;
                for(auto j : ve){
                    if(i == j)continue;
                    temp |= a[j];
                }
                answer = max(answer , temp);
            }
            cout << answer << " " << mi_2 << endl;
        }
    }
    return 0;
}