次のように定義されている問題を解決しようとしています。
キャンディーは 1 から 1e6 までの数字で表されます。1 から k 個までのキャンディーを持っている人は、k 個のキャンディーを持っていると言われます。
たとえば、ある人がキャンディー 1、2、および 6 を購入した場合、その人はキャンディー 2 個のセットを持っています。
与えられた 2 種類の操作: x を食べる、x を買う、x はキャンディーの数を表します。x を購入すると、x の数量が 1 だけ増えます。x を食べると、x の量が 1 だけ減少します。
各操作について、質問に答えてください。私が今持っているキャンディーのセットのサイズはどれくらいですか?
これを行うための最も効率的な方法を見つけようとしています。私が考えた解決策は以下のとおりです。
count[i] でサイズ 1 ～ N の配列を定義します。ここで、N はキャンディーの最大数です。count[i] には、これまでに持っていた i 番のキャンディーの数が格納されます。
Fenwick[i] をサイズ 1 ～ N の配列とします。ここで、N はキャンディーの最大数です。この配列は、フェンウィック ツリーを構築して、コレクション内のキャンディーの累積合計を格納するためのものです。この累積合計は count 配列を使用しません。累積合計は、1 の数量をカウントします (各 1 は、キャンディー x が私のコレクションに存在することを示します)。たとえば、5 個のキャンディーのセットがある場合、1 から 5 までの累積合計は 5 です。10 個のキャンディーのセットがある場合、1 から 10 までの累積合計は 10 です...
購入操作の場合、キャンディー x がまだコレクションにない場合は、インデックス x から始まる累積合計に 1 を追加します (これはフェンウィック ツリーによって処理されます)。それ以外の場合は、count[x]++ を実行します
Eat 操作の場合、count[x]-- を実行します。count[x] が現在 0 の場合、インデックス x から始まる累積合計から 1 を減らします (これはフェンウィック ツリーによって処理されます)。
これで、挿入と削除の部分が決まりました。難しいのは、現在コレクションにあるキャンディーのセットのサイズを取得する方法です。
毎回 2 の累乗でクエリ インデックスをインクリメントしながら、1 から i までの累積合計が i に等しい最大のインデックス i をフェンウィック ツリーにクエリしようとしました。
キャンディーの有効なセットである最大のインデックス j と、キャンディーの無効なコレクションである最小のインデックス k を取ります。次に、j から k までループし、各反復でフェンウィック ツリーをクエリします。ループが無効なコレクションに到達したら、中断して回答を出力します。
これはうまくいくように思えます。ただし、これは確かに効率的な方法ではありません。より良い解決策を教えてくれる人はいますか? 前もって感謝します。
編集（解決策）：
挿入と削除に対する私のアプローチは正しかった。キャンディーのコレクションを間違った方法で探していたというだけです。この場合、最大数 x が必要です。ここで、query(x) = x (query(x) は 1 から x までの累積合計を返します)。したがって、二分探索を使用して x の有効な最大値 (query(x) = x) を見つけることができます。これを実現するには、追加の変数を保持して、query(x) が有効なコレクションを提供する x の最後の値を追跡する必要があります。
解の複雑さ: O(log^2(N))