コンテンツにスキップ

逆順処理

タグ「逆順処理」の記事 1 件

ABC477 D - Masking Tape

NN 個のマスが一列に並んでいて、はじめはすべて色 a でタイルは置かれていません。次の 2 種類のクエリを QQ 個処理したあとの、各マスの色を求める問題です(N,Q≤3×105N, Q \le 3 \times 10^5)。

  • 1 X:マス XX のタイルの有無を切り替える。
  • 2 C:タイルが置かれていないすべてのマスの色を CC に変える。

タイプ 2 のクエリのたびにタイルのないマスを全部塗り直すと、O(NQ)O(NQ) かかって間に合いません。

そこでクエリを後ろから見ていきます。各マスの最終的な色は、そのマスにタイルがなかった最後のタイプ 2 のクエリで決まります。なので、後ろから見て最初に当たった「そのマスにタイルがない時点のタイプ 2」の色が答えです。一度色が決まったマスは、それより前のクエリの影響を受けません。

具体的には次のようにします。

  1. まずクエリを前から処理して、タイルの状態だけを追い、最後の時点でタイルのないマスの集合 UU を求めます。
  2. はじめの状態を「全マスを a に塗るタイプ 2 のクエリ」とみなして先頭に加えます。
  3. クエリを後ろから処理します。
    • タイプ 2 なら、UU のマスをすべてその色に決めて、UU を空にします。
    • タイプ 1 なら、マス XX の色がまだ決まっていない場合だけ、タイルの切り替えを取り消します(UU に XX があれば除き、なければ加える)。

UU に入るのは色が決まっていないマスだけで、各マスの色が決まるのは 1 回だけです。また UU に加えられるのはタイプ 1 のクエリ 1 回につき高々 1 個なので、全体で O(N+Q)O(N + Q) 回の集合操作で済みます。

cLay
ll@N,@Q,t[Q]={97};string S(N,'!');set<ll>s;rep(i,N)s.insert(i);rep(i,1,Q+1){ll@X;if(X-1){char@C;t[i]=C;}else{ll@Y--;if(!s.insert(Y).second)s.erase(Y);t[i]=-Y;}}rrep(i,Q+1){if(t[i]>0){for(ll p:s)S[p]=t[i];s.clear();}else if(S[-t[i]]<'$')if(!s.insert(-t[i]).second)s.erase(-t[i]);}wt(S);

cLay(C++ っぽいコードを C++ に変換するツール)で書いています。ll@N のように変数名の前に @ を付けると、宣言と同時に標準入力から読み込みます。ll@Y-- は読み込んだ直後に 1 減らして 0 始まりにしています。rep(i, 1, Q + 1) は i=1,…,Qi = 1, \ldots, Q、rrep(i, Q + 1) は i=Q,…,0i = Q, \ldots, 0 のループで、wt は出力です。

t[i] に ii 番目のクエリを記録しています。タイプ 2 なら色の文字コード(正の値)、タイプ 1 なら −Y-Y (YY は 0 始まりのマス番号)を入れます。t[0] = 97 は、はじめの状態を表す「a に塗るクエリ」です。

S は色がまだ決まっていないマスを '!' にしておき、S[-t[i]] < '$' で未決定かどうかを判定しています。集合 s の切り替えは、insert が失敗したら(すでにあったら)erase する形で書いています。

Python
N, Q = map(int, input().split())
queries = [("2", "a")]
untiled = set(range(N))
for _ in range(Q):
t, x = input().split()
if t == "1":
x = int(x) - 1
if x in untiled:
untiled.remove(x)
else:
untiled.add(x)
queries.append((t, x))
ans = [""] * N
for t, x in reversed(queries):
if t == "2":
for p in untiled:
ans[p] = x
untiled.clear()
elif not ans[x]:
if x in untiled:
untiled.remove(x)
else:
untiled.add(x)
print("".join(ans))

cLay 版と同じ処理です。はじめの状態を ("2", "a") としてクエリの先頭に入れ、ans が空文字列のマスを色が未決定のマスとして扱っています。