Hints: Count Good Subarrays
Try to restate the condition in a way that focuses on one element inside the subarray.
If a subarray is good, there exists an index $i$ inside it such that:
$$ \text{OR}(\text{subarray}) = \text{nums}[i]. $$
What does that equality force about bits where $\text{nums}[i]$ has a $0$?
Answer to Hint 1: If $\text{OR} = \text{nums}[i]$, then for every bit $b$ with $(\text{nums}[i])_b = 0$, the OR cannot have a $1$ at $b$. So every element in the subarray must also have bit $b = 0$.
So for a fixed $i$, the “bad events” are positions $j$ where $\text{nums}[j]$ has a $1$ in some bit that $\text{nums}[i]$ has as $0$. Those positions cannot be included.
How can you use this to find the farthest you can extend a subarray containing $i$ to the left/right while keeping $\text{OR} = \text{nums}[i]$?
Answer to Hint 2: For each bit $b$, if $\text{nums}[i]$ has bit $b=0$, then the subarray must avoid any index where bit $b=1$. So:
- The left endpoint must be after the nearest index to the left with that forbidden $1$.
- The right endpoint must be before the nearest index to the right with that forbidden $1$.
If you can quickly query, for each bit, “nearest position with bit $1$ on the left/right”, then you can compute an interval $[L_i, R_i]$ such that any subarray $[l,r]$ containing $i$ and staying within $[L_i, R_i]$ satisfies the bit constraints.
But if you count all such subarrays for every $i$, what pitfall appears when the OR value occurs multiple times in the same subarray?
Answer to Hint 3: Overcounting. If a good subarray has $\text{OR} = v$ and $v$ appears multiple times inside it, then several indices $i$ with $\text{nums}[i]=v$ could “claim” it.
One clean fix is to choose a unique representative for each good subarray, e.g. the first (leftmost) occurrence of the value $v=\text{OR}$ inside that subarray.
So for each index $i$, in addition to bit constraints, enforce: “$i$ is the first occurrence of $\text{nums}[i]$ inside the subarray.”
How do you translate that into a constraint on the left endpoint (l)?
Answer to Hint 4: “$i$ is the first occurrence of $\text{nums}[i]$ in $[l,r]$” means there is no same value $\text{nums}[i]$ in $[l, i-1]$. Equivalently:
$$ l > \text{prevSame}(i), $$
where $\text{prevSame}(i)$ is the previous index with the same value (or $-1$ if none).
Now combine this with the bit-based left restriction to get a final lower bound:
$$ l \ge \text{leftBound}[i]. $$
Similarly, the bit constraints give an upper bound:
$$ r \le \text{rightBound}[i]. $$
Once you have $\text{leftBound}[i]$ and $\text{rightBound}[i]$, how many subarrays are “claimed” by index $i$?
Answer to Hint 5: Count choices independently:
- $l$ can be any index in $[\text{leftBound}[i], i]$, so there are $i-\text{leftBound}[i]+1$ options.
- $r$ can be any index in $[i, \text{rightBound}[i]]$, so there are $\text{rightBound}[i]-i+1$ options.
Contribution of $i$ is the product of those counts. Summing over all $i$ gives the answer.
The remaining question is computing the bounds fast. How can you compute $\text{leftBound}[i]$ in $O(30)$ time per $i$ with a left-to-right scan?
Answer to Hint 6: Maintain, for each bit $b$, the most recent index where bit $b$ was $1$. Call it $\text{prevOne}[b]$.
When you’re at index $i$:
- For every bit $b$ where $\text{nums}[i]$ has $0$, the subarray must start after $\text{prevOne}[b]$. So you take the maximum of those $\text{prevOne}[b]$ over “forbidden” bits.
- Also enforce $l > \text{prevSame}(i)$ for the “first occurrence” rule.
Then set $\text{leftBound}[i] = 1 + \max(\text{prevOne}[b]\ \text{over forbidden bits},\ \text{prevSame}(i))$.
After processing $i$, update $\text{prevOne}[b]$ for bits where $\text{nums}[i]$ has $1$, and update $\text{prevSame}$ via a hash map from value $\to$ last index.
How do you compute the right bounds symmetrically?
Answer to Hint 7: Do a right-to-left scan maintaining $\text{nextOne}[b]$ = nearest index to the right where bit $b$ is $1$.
For index $i$, for every bit where $\text{nums}[i]$ has $0$, the subarray must end before $\text{nextOne}[b]$. So:
$$ \text{rightBound}[i] = -1 + \min(\text{nextOne}[b]\ \text{over forbidden bits}). $$
Then update $\text{nextOne}[b]$ for bits where $\text{nums}[i]$ has $1$.
At that point you can compute all contributions in $O(n \cdot 30)$, which is fine for $n \le 10^5$.