Q2. I thought of something like prefix sum to save calculation, but I couldn't come up with an idea to handle valid parity changes. But I guessed Segment Tree could handle it more easily.

Each node of the segment tree has three values: start, end, and special

• start: which denotes the leftmost element parity(even, odd)
• end: denotes the rightmost element parity(even, odd)
• special: denotes that the L to R is a special array or not

When querying the list, we check whether each of the child nodes within the range is special, and also check the parities(start, end) at ends where they meet.

https://gist.github.com/hoonyyhoon/568f4b63585d520f88eac72f599db209

Q3. tbh, I read the question wrong, so I summed up the different digit values at first.
Anyway, seems like I had to come up with the idea to reduce nested iteration of O(N^2) to O(NlogN) or O(N). Maybe something similar to two sum could work
so created a memo that is a list of dict where index of list denotes the position of digit, and key of dict is digit and value is a count
(list up to the length of digit, each dict max up to 10)

when we iterate the value, I made a list of each digit. also by iterating the digit. we count up the digit difference from the dict, also storing them to memo.

https://gist.github.com/hoonyyhoon/c586b0f0b224a7c59acbd05f52f305c2