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

Question

给定一个整数数组A，我试图找出在给定位置j，A[j]从A中每个i=0到i=j出现多少次。我设计了一个解决方案，

如下所示

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 大小相同的数组B和一个映射C。对于B[j]中的每个j，请跟踪j之前A[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;

，然后在该队列中查找正确的位置。你仍然需要一个地图，但是在下面你只有一个这些指针的列表，在查询时，你在地图中查找A[i]，然后在我>索引&&next &&iindex时浏览列表。当然，如果 logn 是必须的，那么这将失败，因为列表查找在最坏的情况下为 n。