子数组按位与值位K的数目 logTrick + 二分 leetcode 134双周赛

题目：

题解：

logTrick：在O( nlogv )的时间复杂度枚举出所有子数组按位and或or操作的值。

代码：

    //~01~泛型查找
    int lf(int l,int r,vector<int>&nums,int target){
        int mid;
        while(l<r){
            mid=(l+r)>>1;
            if(nums[mid]>=target)r=mid;
            else l=mid+1;
        }
        if(nums[l]==target)return l;
        return -1;
    }
    //~10~泛型查找
    int rf(int l,int r,vector<int>&nums,int target){
        int mid;
        while(l<r){
            mid=(l+r+1)>>1;
            if(nums[mid]<=target)l=mid;
            else r=mid-1;
        }
        return l;
    }

    long long countSubarrays(vector<int>& nums, int k) {
        long long ans=0;
        for(int i=0,I=nums.size();i<I;i++){
            for(int j=i-1;j>=0;j--){
                if((nums[j]&nums[i])==nums[j])break;
                nums[j]=(nums[i]&nums[j]);
            }
         //在这个位置可以依次得到所有子数组，且0~1为所有子数组按位and的结果，且单调递增。
         //这里在每一个子数组上找出值为k的数量，也就是有序数组中有多少个k元素。
            if(lf(0,i,nums,k)!=-1){
                ans+=rf(0,i,nums,k)-lf(0,i,nums,k)+1;
            }
        }
        return ans;
    }

题后反思：

~01~二分和~10~二分每次>>1都是将mid指针落在潜在的0的位置。