И всё же, багом назвать такое нельзя.

С первого взгляда, конечно, разница незаметна, и списать различие можно разве-что на причуды оптимизатора. Но, внезапно, вы написали Фенвика на мэпе (хотя зачем, ведь частота не превышает количества элементов в массиве?). Следственно меняется порядок добавления чисел в дерево (которое внутри map'а): от меньших к большим, или наоборот. А это уже может повлиять на внутреннюю работу структуры, например, увеличить количество вращений.

В общем, предугадать такое нельзя, но и удивляться особо не стоит =)

Раз уж подняли тему про map, хочу спросить. Если у нас есть мап <X, Y> и мы интересуемся значением мапа на объекте Х, для которого не определено значение, то для этого используется конструктор по умолчанию для Y?

Что-то подобное частенько бывает.. В задаче Div1 A на поиск точек прямоугольного треугольника по длине катетов (у которого все стороны не параллельны осям X и Y) мне помогло пройти упавшее решение изменение в коде — из for(int x = -1; x >= -1000; x--) в (int x = 1; x <= 1000; x++), так как возможно два ответа когда известны две точки треугольника, хотя потом я понял, что это не баг, а просто не попался тест, ответом на который будет что-то вроде

0 0 -12 -16 -12 9

Т.е. как в первом решении Х)

P.S. Обвал решения на последнем тесте — жестоко...

кстати есть такой трюк. В коде из посылки

for (i=n;i>0;i--)
{
    mp[a[i]]++;
    s[i]=mp[a[i]];
}

в цикле идет по 2 обращения к мапе. Но можно обойтись и одним, ведь оператор [] возвращает ссылку:

for (i=n;i>0;i--)
{
    int& it = mp[a[i]];
    s[i]= ++it;
}

вот этот код тоже лучше переписать:

while (v>0)
{
    s+=t[v];
    v=(v & (v+1))-1;
}

t[v] вставляет в мапу элементы с нулевыми значениями. Лучше использовать итераторы:

while (v>0)
{
    map<int, int>::iterator it = t.find(v);
    if (it != t.end()) s+=it->second;
    v=(v & (v+1))-1;
}

Тоже хотел задать вопрос про особенность структур данных в С++.

Почему данный код валится по времени, а этот проходит все тесты? Multiset так долго работает?

Замена map на unordered_map делает ОК ваше ТЛ решение.

http://codeforces.me/contest/459/submission/7494177

Асимптотика уменьшилась в log раз, ибо unordered_map амортизировано работает за О(1).