Official

G - Range Set Modifying Query Editorial by kyopro_friends

問題原案：kyopro_friends

この問題は Segment Tree Beats と呼ばれる、セグメントツリーを応用したデータ構造を用いることで解くことができます。

遅延セグメントツリーで解こうとする試み

この問題を遅延セグメントツリーを用いて解くことを考えてみます。（遅延セグメントツリーの実装方法にはいくつかバリエーションがありますが、ここでは AtCoder Library(ACL) における実装に基づいて説明します）

最初に自然に思いつくのは以下のようなデータの持ち方でしょう：

  • ノードが持つ情報
    • 対応する区間の集合の要素数の最大値 \(M\)
    • 対応する区間の集合の要素数の最大値を達成する個数 \(C\)
  • 写像が持つ情報
    • 写像を \(f(x)=(x \setminus a)\cup b\) と表したときの \((a,b)\)

このようなデータの持ち方をした場合、op, e, id, composition は定義することができますが、mapping を適切に定義することができません。

一般に(遅延)セグメントツリーを用いて問題を解く場合は、ノードが持つ情報を増やすことでこのような事態を避けることを目指しますが、この問題では計算量を増やすことなく解決することはおそらくできません。

Segment Tree Beats のアイディア

「mapping が \(f,x\) のみから計算できない場合、そのノードの写像 \(f\) を子ノードに伝播して子ノードで再帰的に mapping を行い、自身のノードは再計算された子ノードから op で計算する」というのが Segment Tree Beats の本質的なアイディアです。この方法は、クエリを処理する過程全体で「mapping が \(f,x\) のみから計算できない」が起こる回数が十分少ないことを保証できれば高速です。

本問の解法

以下のようにデータ構造を定義します

  • ノードが持つ情報
    • 対応する区間の集合の和集合 \(O\)
    • 対応する区間の集合の積集合 \(A\)
    • 対応する区間の集合の要素数の最大値 \(M\)
    • 対応する区間の集合の要素数の最大値を達成する個数 \(C\)
  • 写像が持つ情報
    • 写像を \(f(x)=(x \setminus a)\cup b\) と表したときの \((a,b)\)
  • mapping が成功する条件
    • \((O \setminus A)\cap (a \cup b)=\emptyset\)
      • 直感的には「削除・追加対象の要素はそれぞれ、区間内の集合の全てに含まれているか、いずれにも含まれていない」を意味する。

このように定義すると、mapping が失敗するごとに \(O\setminus A\) のサイズが真に減少します。また、\(1\) 回のクエリにより \(O\setminus A\) のサイズが増加するノードは \(O(\log N)\) 個であり、その増分は高々 \(1\) です。よって mapping が失敗する回数は全体で \(O(N \max x+Q\log N)\) であり、クエリ全体を \(O((N+Q)\log N + N\max x)\) 回のセグ木の操作で処理することができます。

集合をbit列で保持することで集合演算は \(O(1)\) で行えるとみなせ、\(O((N+Q)\log N + N\max x)\) 時間でこの問題を解くことができます。

実装例(C++/データ構造の定義・関数の実装部分のみ)

using ll=long long;
struct S{
	// aaa=\cap S_i, ooo=\cup S_i
	// max=\max(#S_i), cnt=#{i|#S_i=max}
	ll aaa,ooo;
	int max,cnt;
	bool fail;
};
struct F{
	// f(x)=(x \cap aaa) \cup ooo;
	ll aaa,ooo;
};
S e(){
	return{-1,0,0,0,false};
}
F id(){
	return{-1,0};
}
S op(S x,S y){
	S ret;
	ret.aaa=x.aaa&y.aaa;
	ret.ooo=x.ooo|y.ooo;
	if(x.max>y.max){
		ret.max=x.max;
		ret.cnt=x.cnt;
	}else if(x.max<y.max){
		ret.max=y.max;
		ret.cnt=y.cnt;
	}else{
		ret.max=x.max;
		ret.cnt=x.cnt+y.cnt;
	}
	ret.fail=false;
	return ret;
}
S mapping(F f,S x){
	if((x.ooo^x.aaa)&(~f.aaa|f.ooo)){
		//fail
		return {0,0,0,0,true};
	}
	S ret=x;
	ret.max-=__builtin_popcountll(ret.aaa&~f.aaa);
	ret.aaa&=f.aaa;
	ret.ooo&=f.aaa;
	ret.max+=__builtin_popcountll(~ret.ooo&f.ooo);
	ret.aaa|=f.ooo;
	ret.ooo|=f.ooo;
	return ret;
}
F composition(F g,F f){
	F ret;
	ret.aaa=f.aaa&g.aaa;
	ret.ooo=(f.ooo&g.aaa)|g.ooo;
	return ret;
}

// atcoder::lazy_segtree のメンバ関数 all_apply を以下のように変更
void all_apply(int k, F f) {
    d[k] = mapping(f, d[k]);
    if (k < size) {
        lz[k] = composition(f, lz[k]);
        if (d[k].fail) push(k), update(k);  // <-- add
    }
}

参考文献

Segment Tree Beats を用いない別解

「整数列を保持し、区間最大値とその個数を取得でき、区間加算が可能な遅延セグメントツリー」を用意し、各集合の要素の個数を管理することを考えます。

クエリによる操作で真に要素が追加/削除される区間がわかれば、それらの区間に対してのみ操作を行うことでこの問題を解くことができます。すなわち、例えばクエリにより「\(S_3,\ldots,S_{12}\) に \(x\) を追加」とするとき、すでに \(S_5,S_6,S_{10}\) に \(x\) が含まれていれば真に影響を受ける区間は \([3,4],[7,9],[11,12]\) であり、これらの区間に対してのみ区間加算の操作を行うことにすれば、先程述べた遅延セグメントツリーでクエリを処理することができます。

これを実現するために、「01列を保持し、区間内の値が全て0/1であるかを取得でき、区間代入が可能な遅延セグメントツリー」を60本用意し、各値が各集合に含まれるかを管理します。この遅延セグメントツリーの上で二分探索することで真に影響を受ける区間を列挙することができます。

60本のセグ木における隣接する要素の値が異なる箇所の個数を考えることで、操作する区間の個数はクエリ全体で \(O(Q)\) となることがわかります。よってこの問題を \(O(Q\log N+N\max x)\) で解くことができました。

実装上は適切にまとめることで1本の遅延セグメントツリーで実現することができます。

この別解はテスターの sheyasutaka さんによるものです。

posted:
last update: