This is somewhat of a joke, but you can solve it by using a Lazy Segment Tree to manage the numbers of uppercase and lowercase letters in each interval within the string. (You can naively update which of A, B, …, Z each letter is.)

Sample Implementation(C++)