По заданному индексу i,j(j>=i) Как найти частоту A[j] в подрешетке (i,j)?

Учитывая массив A целых чисел, я пытаюсь выяснить в данной позиции j, сколько раз A[j] встречается с каждым i=0 до i=j в A. Я разработал решение, как показано ниже

map<int,int> CF[400005];
for(int i=0;i<n;++i)
{
   cin>>A[i];
   if(i!=0)
      CF[i-1] = CF[i];
   ++CF[i][A[i]]; 
}

чем я могу ответить на каждый запрос во время входа в систему. Но эта процедура использует слишком много памяти. Есть ли способ сделать это, используя меньше памяти?

для более ясного понимания вы можете увидеть проблему, которую я пытаюсь решить http://codeforces.com/contest/190/problem/D

Источник

2 ответа

Решение

Создать массив B того же размера, что и A и карта C, Для каждого j в B[j] отслеживать количество случаев A[j] до j, В C отслеживать последнее вхождение данного элемента. Затем вы отвечаете на запросы в постоянное время, и это требует только O(n) памяти.

Извините за мой псевдо-C++.

map<int,int> C;
int B[n]; // zeros

for(int i=0;i<n;++i)
{
    cin >> A[i];
    int prev = C[A[i]]; // let me assume it gives -1 if no element

    if (pref == -1) // this is the fist occurrence of B[i]
        B[i] = 1;
    else // if not the first, then add previous occurrences
        B[i] = B[prev] + 1 

    C[A[i]] = i; // keep track where the last info about A[j] is
}
Источник

Не тратите на это слишком много времени, но, возможно, вместо использования карты будут все позиции, используйте список, в котором для каждого элемента вы ставите точки, в которых изменяется счет этого элемента, что-то вроде этого:

struct count_info
{
    int index;
    int count;
    count_info* next;
};
...
std::map<int, count_info*> data;

, а затем найдите правильную позицию в этой очереди. Вам по-прежнему нужна одна карта, но под ней у вас будет только список этих указателей, и по запросу вы просматриваете A[i] на карте, а затем просматриваете список, пока i > index && next && i < next->индекс. Конечно, если logn является обязательным, то это не сработает, потому что поиск по списку в худшем случае n.

Источник
Другие вопросы по тегам