给定索引i，j(j>=i)，如何在子数组(i，j)上求出A[j]的频率？

Question

给定一个数组A的整数，我试图找出在给定的位置j，在A中的每个i=0到i=j中Aj发生了多少次，我已经设计了如下所示的解决方案

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问题

Answer 1

创建一个与A大小相同的数组C和一个映射C。对于B[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
}

Answer 2

并没有给出太多的时间，但是也许不是使用一个地图将所有的位置，而是使用一个列表，对于每个元素，您放置的点，该元素的计数变化，这样的东西：

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

，然后在队列中查找正确的位置。您仍然需要一个映射，但是在下面只需要一个这些指针的列表，在查询时，您可以在地图中查找Ai，然后在I> index & next && go；I&go；next->索引时遍历这个列表。当然，如果logn是必须的，那么这就失败了，因为列表查找在最坏的情况下是n。