Cow Check Ups is a more advanced counting problem because the operation changes an interval, but most of the array outside that interval stays the same. The main strategy is to separate what changes from what does not.
Start with the base matches
Before considering any operation, count how many positions already match.
base = number of i where a[i] == b[i]Then build a prefix array so the number of original matches inside any interval can be found quickly.
matchesInside(l, r) = pref[r] - pref[l - 1]What an interval reversal changes
For a chosen interval [l, r], positions outside the interval keep their original match status. Inside the interval, the reversed values create new possible matches.
newTotal = base - oldMatchesInside + newMatchesInsideThis is the entire contribution idea. Do not recompute the full array for every interval; only replace the interval's old contribution with its new contribution.
Why grouping by l + r helps
When an interval is reversed, a position i inside the interval receives a value from position j where:
i + j = l + rThat means intervals with the same l + r share a useful diagonal relationship. Scanning by that sum lets the code reuse temporary prefix counts for possible new matches.
Common mistakes
- Counting all matches from scratch for every interval.
- Forgetting to subtract old matches inside the changed interval.
- Mixing 0-indexed and 1-indexed prefix formulas.
- Using
intfor an answer array that counts many intervals.
Practice prompt
Take arrays a = [1, 2, 3] and b = [3, 2, 1]. List every interval reversal, compute the new number of matches, and group the intervals by their l + r value.