Блог пользователя Raghavan_CP

Автор Raghavan_CP, история, 16 месяцев назад, По-английски

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)

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
16 месяцев назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

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 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -10 Проголосовать: не нравится

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 месяцев назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

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 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.