c++ - 给定索引 i,j(j>=i) 如何找到子数组 (i,j) 中 A[j] 的频率？

Question

给定一个整数数组 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

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
}