【CF】CF-1878E真题Iva&Pav线段树+二分题解

题目传送门：Iva & Pav - 洛谷

题目大意

给定数组a和其长度n，有q次询问，每次给出,求最小的r使得

? （无解输出-1）

(注：本文出现的所有符号全部代表位与运算！)

（）

思路及性质

首先，题目中要求的运算是位与运算，如果还不了解可以戳：

C/C++二进制、位运算详解_c++二进制数表示和运算-CSDN博客

根据位与运算的法则，我们很容易就可以推出：

---------具体证明：

·若, 则 ，因为它们在二进制下的数字完全相同。

·若, 即使其中一方在二进制下的数位多出几个1，但另一方此位为0，不会扩大结果。

相反地，若一个位上本来是1，另一方却是0，则只会使结果变小。

----------

想明白这个问题，我们就能推断，若

则在一定的情况下，

想到这里，理一下思路：

我们可以用二分查找r，若?则记录答案，往小了找；

若，则往大了找；

若没有找到，则输出-1。

现在的问题是，如何在大约的时间里求?呢？

我们想到了线段树。?

由于位与运算满足交换律，且根据f函数的定义，

所以便有了维护线段树 tr，使

具体不知道怎么实现？看代码就完了！

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
#define MaxN 200005
#define For(i, j, k) for(int i = j; i <= k; i++)

int t, n, q;
int a[MaxN];

struct Node{
    int l, r, num;
}tr[MaxN*4];    //线段树
//注：用tr数组表示线段树，tr[x*2]即x的左儿子，tr[x*2+1]即x的右儿子

void inline build(int x, int l, int r){    //建立区间x，范围[l,r]
    tr[x].l = l, tr[x].r = r;
    if(l == r){              //如果只有一个数
        tr[x].num = a[l];    //结果就是它本身
        return ;
    }
    int mid = (l + r) / 2;
    build(x*2, l, mid);        //否则先建左半部分
    build(x*2+1, mid+1, r);    //再建右半部分
    tr[x].num = tr[x*2].num & tr[x*2+1].num;    //两部分进行位与运算即答案
}

int inline query(int x, int l, int r){        //在区间x中查询f(l, r)
    if(tr[x].l == l && tr[x].r == r)          //找到了
        return tr[x].num;                     //直接返回
    int mid = (tr[x].l + tr[x].r) >> 1;
    if(r <= mid) return query(x*2, l, r);     //如果区间在mid左边，直接到左边找
    if(l > mid) return query(x*2+1, l, r);    //如果区间在mid右边，直接到右边找
    int A = query(x*2, l, mid);        //否则存储左边的结果
    int B = query(x*2+1, mid+1, r);    //存储右边的结果
    return A & B;    //两者运算即答案
}

int main()
{
    cin >> t;
    while(t--){        //多测
        cin >> n;
        For(i, 1, n) cin >> a[i];
        build(1, 1, n);    //建树
        cin >> q;
        while(q--){
            int L, k;
            cin >> L >> k;
            int l = L, r = n;
            int ans = -1;
            while(l <= r){        //二分r
                int mid = (l + r) >> 1;
                int abab = query(1, L, mid);
                if(abab < k){     //f(l, r) < k，即r太大
                    r = mid - 1;
                }else if(abab >= k){    //r太小
                    ans = mid;
                    l = mid + 1;
                }
            }
            cout << ans << ' ';
        }
        cout << endl;
    }
    return 0;
}

总结?

黄题偏上吧，了解一些最基础的数据结构即可。

二分的思路思维难度不高，剩下的用分块、线段树做都行。

今天就说那么多，最后，制作不易，如果你觉得这篇文章还不错的话，麻烦点个收藏点个关注，这是免费的，您随时可以取消。你们的支持是作者最大的动力！