Разбор добавил Александр Чистяков

Заведём массив длины n+1 в i-той ячейке которого будем хранить разницу между количеством мальчиков и девочек с номерами от 1 до n. 
Покажем, как будет заполняться этот массив при определённых входных данных:
   a b b a b a b a b b b b a 
0 -1 0 1 0 1 0 1 0 1 2 3 4 3
(Изначально перевес отсутствует (и мальчиков и девочек нет) )
Данный массив легко заполняется одновременно с процессом считывания строки (то есть за O(n) ).
Чтобы на отрезке [m; n] количество мальчиков и девочек совпадало, надо чтобы перевесы количества мальчиков над девочками на отрезках [1; m] и [1; n] совпадали. При чём это условие одновременно является необходимым и достаточным.
Чтобы найти требуемый ответ надо сначала подсчитать количество каждых из значений массива (легче всего сделать при помощи быстрой сортировки с последующим однократным проходом по новому массиву, или с использованием сортировки подсчётом, которая в этой задаче наиболее оправдана).
Теперь, зная количество одинаковых состояний в массиве легко определить количество удачных пар, посчитав количество способов для каждого значения X выбрать два элемента (X*(X-1)/2).

Покажем как получить ответ для рассмотренного примера:
Значение  | Кол-во знач. | Кол-во пар |
-1          1              0
0           5              10
1           4              6
2           1              0
3           2              1
4           1              0
Слкедовательно ответ в задаче 0 + 10 + 6 + 1 = 17