Raghavan_CP's blog

By Raghavan_CP, history, 16 months ago, In English

A subarray is considered compromised if the bitwise OR of all elements in any subarray is present in the subarray itself. Find the number of compromised subarrays in a given array of positive integers.

A subarray is defined as any contiguous segment of the array.

Example arr = [2, 4, 7] Answer = 5

Please help with the processing idea?

More Questions: Given an alphabet of size m, find the number of passwords of length n such that no character appears k or more times consecutively.(hard)

Given a graph, perform DFS traversal and output all distinct valid outputs (such as all unique DFS traversal paths or orders depending on the specific constraint). (Medium)

  • Vote: I like it
  • -6
  • Vote: I do not like it

| Write comment?
»
16 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

First thing is observe a fact that if you OR two numbers the value increases or stays the same if they are equal. For each index i, you need to find a range [L,R] where there are no bad bits in reference to a[i] , meaning a bit is zero in a[i] but not in the range [L,R], if there is a bad bit , OR won’t be equal to a[i], you also need when a[i] appears again in the list to avoid duplicate counting, let’s assume a[k] is same as a[i] and k <=R, if so we’ll count all sub arrays that start from L or after, end between i and k-1 inclusive , if there is no such k then you count ending up to R from i. This you would do for range 1 to n and sum it up

  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it -13 Vote: I do not like it

    i dont think stack would work

  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it -10 Vote: I do not like it

    i think maintain prefix array bitwise means prefix[i][j] tells cnt of numbers upto index which have jth bit set

    now for finding l,r you should do binary search like for sets all unset bits B in a[i] prefix[i][B] should be same as prefix[r][B]

    i hope you understood

»
16 months ago, hide # |
← Rev. 2  
Vote: I like it -10 Vote: I do not like it

Find the nearest element to the left and right of each element, which has a bit which is set while the same bit is unset in our concerned number. You can use a monotonic stack for that.

Then, for each element, it's just subarray combinations keeping the central element. For same element occuring in one of these extensions, subtract accordingly

»
16 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

The most effortless solution i can think is by using segment tree. Let's say ith element is OR of the some subarray then we can find the lower and upper bound. We can do binary search in Segment Tree, we are able to do this because we know doing prefix OR is always monotonically increasing.

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ARUN ios::sync_with_stdio(false); cin.tie(nullptr);

class SegmentTree {
private:
    vector<int> a, seg;
    int n;

    int merge(int x, int y) {
        return x | y;
    }

    int neutral() {
        return 0;
    }

    void build(int node, int l, int r) {
        if (l == r) {
            seg[node] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);
        seg[node] = merge(seg[2 * node], seg[2 * node + 1]);
    }

    int query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return neutral();
        if (ql <= l && r <= qr) return seg[node];
        int mid = (l + r) / 2;
        return merge(
            query(2 * node, l, mid, ql, qr),
            query(2 * node + 1, mid + 1, r, ql, qr)
        );
    }

public:
    SegmentTree(const vector<int>& input) {
        a = input;
        n = a.size();
        seg.resize(4 * n);
        build(1, 0, n - 1);
    }

    int query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

void solving() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (auto& x : arr) cin >> x;

    SegmentTree ST(arr);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int OR = arr[i];
        // find lower bound such that or of [lb ... i] == OR
        int l = 0, r = i, lb = i;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (ST.query(mid, i) == OR) {
                lb = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        // find upper bound such that or of [i ... ub] == OR
        l = i, r = n - 1;
        int ub = i;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (ST.query(i, mid) == OR) {
                ub = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        // Now we have something like [lb ..... i .... ub]
        int count = (i - lb + 1) * (ub - i + 1);
        ans += count;
    }
    cout << ans << '\n';
}

int32_t main() {
    ARUN;
    int t = 1;
    cin >> t;
    while (t--) solving();
    return 0;
}

»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

for P1,

maintain a array for storing the most recent index the bit 'b' is on this, way you will find the L and similarly find the R as well.

L = max(bit_prefix[i], L) where i is ith bit where the current index bit is off.

R = min(bit_sufix[i], R), where i is ith bit where the current index bit is off.