0クリアするためだけに遅延セグ木を書かない

需要

三井住友信託銀行コンテスト2019-E を想定解とは違う方法で解いていて以下のような操作を高速に($O(\log (N))$くらいで)できる配列が欲しくなりました

• 一点代入/一点取得 (普通の配列の操作)
• 全ての要素を0に変える

こういう状況はたまにありそうです。
「区間代入だから遅延セグ木 !」と思って遅延セグ木を書いても良いんですが遅延セグ木は計算量にlogがつく上に実装が面倒で、ライブラリで殴れば別ですがこの単純な遅延セグ木である程度慣れていても10~15分は実装に飛ぶと思います。(あとバグると大変)

0クリア

この操作をサポートするデータ構造(っぽいもの)を3分で書ける方法を紹介します。

そのアイディアは至ってシンプルで(配列の初期値を0とすると)最後に0クリアされてから一点代入が行われた回数しか配列中に非0の要素は出現しないというものです。
このため

• 一点代入した時にそのインデックスをvector(writtenという名前とする)にでも入れておいく
• 0クリアのときにwrittenに入っている全ての位置に0を代入してwrittenをクリアする

とすると0クリアで見るwrittenの要素数の和は高々一点代入が行われた回数なので全操作のならし計算量が$O(1)$になります。

実装は以下の通りです(C++)

class ZeroClearableArray {
	std::vector<int> data; // 管理している配列そのもの
	std::vector<int> written; // 最後に0クリアされてから一点代入が行われたインデックスが全部入っている
public :
	int n;
	ZeroClearableArray (int n) : data(n), n(n) {}
	int operator [] (int i) { return data[i]; }
	void assign(int i, int val) { data[i] = val; written.push_back(i); }
	void zero_clear() {
		for (auto i : written) data[i] = 0;
		written.clear();
	}
};

これなら3分で書けますね !
計算量からlogが落ちるので銀行コンEの例では遅延セグ木を使ったときと比べて206ms->33msの高速化にもなりました。

kクリア(1)

ところでちょっと工夫すると0クリアに限らず一般の$k$クリアの操作も簡単に実装できます。
配列の要素の値域に含まれない値を一つ$e$ととります。(そんなものがなければ半群をモノイドにする要領で要素にboolフラグを足して無理やり作ってください)

• dataの初期値は$e$にします
• $k$クリアの時には先ほどと同様の手順で書き込まれた所全てを$e$に変えます(そして$k$をどっかに保存します)
• 一点取得の際はdata[i]が$e$なら最後に$k$クリアされたときの$k$(まだされてなければ配列の初期値にしたいもの)を返し、そうでなければdata[i]をそのまま返します
• 一点代入の際は普通にdata[i]に代入します(iは例のvectorに入れておきます)

例えば非負整数を扱う配列(初期値0)とすると$e=-1$ととれて実装は以下のようになります。

class AllAssignableArray {
	std::vector<int> data;
	std::vector<int> written;
	int last_k = 0; // この0は配列の初期値の0
public :
	int n;
	AllAssignableArray (int n) : data(n, -1), n(n) {}
	int operator [] (int i) { return data[i] == -1 ? last_k : data[i]; }
	void assign(int i, int val) { data[i] = val; written.push_back(i); }
	void assign_all(int k) {
		for (auto i : written) data[i] = -1;
		written.clear();
		last_k = k;
	}
};

kクリア(2)

これについて考えていたら$k$クリアをサポートする別の方法を思いついたので乗っけておきます。
こちらは$k$クリアしたときにのみ1進む「時間」を定義し、各要素について最後に一点代入された値(data)と時間(updated_time)を持っておきます
一点取得の際にその要素のupdated_timeが今の時間より前だったら、最後に一点代入された後に$k$クリアされているので最後の$k$クリアの$k$を返します。
そうでなければdataの方を返します。

class AllAssignableArray {
	std::vector<int> data;
	std::vector<int> updated_time;
	int time = 0;
	int last_k = 0; // この0は配列の初期値
public :
	AllAssignableArray (int n) : data(n), updated_time(n) {}
	void assign(int i, int val) { data[i] = val; updated_time[i] = time; }
	int operator [] (int i) { return updated_time[i] < time ? last_k : data[i]; }
	void assign_all(int k) { time++; last_k = k; }
};

まとめ

どれも冷静に考察すれば思いつくことができそうですが、コンテスト中は案外「これは遅延セグ木で解ける !」の方に脳死で飛びつきがちです
これを知って実装時間を省略 !