Блог пользователя Mr.Temirbay

Автор Mr.Temirbay, 10 лет назад, По-русски

Всем добрых суток! Сегодня решил порешать задачи на структуры данных. Встретил задачу на Фенвика. Надо найти количество вхождении числа x в отрезке от 1 до i и от i+1 до n. Помогите чем сможете. Заранее спасибо. Задача здесь.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Можно решить ДО.

Посчитай массив cntback[i], количество чисел от i до n, таких, что они равны a[i]. Это можно сделать так:

for(int i = n; i >= 1; --i)
   Cnt[a[i]]++, cntback[i] = Cnt[a[i]];

Теперь, ты просто пробегаешься циклом от 1 до n, и считаешь вхождение каждого числа от 1 до i. Это можно сделать так:

for(int i = 1; i <= n; ++i) {
    cnt[a[i]]++;
    curcnt = cnt[a[i]];
    ans += количество cntback от i + 1 до n, которые больше чем curcnt
}

Теперь, как посчитать это количество? ДО.

Когда считаем cntback, сразу обновляем его в ДО:

for(int i = n; i >= 1; --i)
   Cnt[a[i]]++, cntback[i] = Cnt[a[i]], upd(1, 1, n, cntback[i], 1);

Это значит, что мы обновляем элемент в дереве с индексом cntback[i], увеличиваем его на 1.

Теперь, подсчет выглядит так:

for(int i = 1; i <= n; ++i) {
    upd(1, 1, n, cntback[i], -1); // нам нужно от i + 1, i + 2, i - тый больше не считаем, отнимаем его
    cnt[a[i]]++;
    curcnt = cnt[a[i]];
    ans += get(1, 1, n, 1, curcnt - 1); // get(v, tl, tr, l, r) - возвращает сумму от l до r
}