Codeforces ラウンド #220 (ディビジョン 2) D ツリー配列 && binary_html/css_WEB-ITnose

/*Title*/

ヒント: n、m、そして m 個の数値を含む配列 nnum を指定すると、配列はデフォルトで小さい値から大きい値の順に並べ替えられ、数値 x を入力します。 , if x が 0 の場合、文字列の末尾に 0 を追加します。x が 1 の場合、文字列の末尾に 1 を追加します。x が -1 の場合は、文字列の添字を nnum 配列の要素と等しくします。 . 先頭が空の文字列です 最後の文字列が空の場合は POOR STACK が出力されます

この質問を見ると、一般的には線分ツリーとツリー配列が考えられます。最初はツリー配列を構築しましたが、結局、多くの操作があり、削除操作では、nnum 配列が非常に大きく、複雑さが 10^12 に相当する場合にのみ実行できました。一般的には2つに分けて、この文字列の任意の位置が空かどうかを基準にツリー配列を作成し、その都度最後に追加するのがポイントです。最初のステップは、バイナリ検索によって削除される最後の文字を検索することです。たとえば、文字列の長さは 7 ですが、実際には位置 8 が検索されます。削除する必要はありませんが、これでもタイムアウトになるため、ツリー配列で削除するときにも2つに分割する必要があると考えていましたが、書き間違え続けて、後でJie Geの発見から学びました。たとえば、現在の文字列は 01010 であり、位置 1、3、および 4 の文字を順番に削除する必要があります。位置 1 を削除すると、文字列は 1010 になります。ツリー配列のノード1のステータスを削除する必要があるので、元の位置3番が位置2になります。 3番を削除すると110になり、元の位置4番が位置Noになりました。 .2 なので、削除されるたびに添字が変わりますが、これまでの数回の操作の後、元の添字が現在の添字に比べて数倍減少していることがわかりました。そのため、nnum[i] - i は実際には、ツリー配列内の削除された要素の位置です。