2

整数の配列 A が与えられた場合、特定の位置 j で、 A の i=0 から i=j までの A[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

4

2 に答える 2

3

および map とB同じサイズの配列を作成します。For each inは、 beforeの出現回数を追跡します。指定された要素の最後の出現を追跡します。次に、クエリに一定時間で回答すると、O(n) メモリだけが必要になります。ACjB[j]A[j]jC

疑似 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
}
于 2014-01-14T10:22:33.827 に答える