Hatena::Grouptopcoder

kuuso1の日記

2014-09-15

ABC014 C AtColor

| 00:47 | ABC014 C AtColor - kuuso1の日記 を含むブックマーク はてなブックマーク - ABC014 C AtColor - kuuso1の日記

http://abc014.contest.atcoder.jp/tasks/abc014_3

  • 閉区間 [0,1000000]の部分区間 [ a_i, b_i ] (i=1 to N) が与えられる
  • もっとも多く含まれている数字の、含まれた回数を答える

(制約)1 ≤ N ≤ 10^5

方針:ヒストグラムを作ってその最大値を求める。その際に、与えられる区間の値をすべて足しているとTLEする。

想定解法はいもす法(公式解説)ですが、知らなかった(思いつかなかった)のでセグメントツリーで解きました。

・区間全域に1を加える代わりに、区間を代表するノードにだけ1を加えます。

・最大値クエリでは、ツリーの下側のノードから再帰的に、両手の大きい方を自分のノードの値とする

 典型的なRange Maximum Queryで求めますが、その際に区間に一様に加算された値を足して自分のノードの値とすることで

 最終的に真値が求められます。(ポイントは左右の大小比較に遅延分が影響しないところですね!)

・計算量  :区間に加算がO( N * log(M) )、最大値クエリ:O(M) (ここでM=1000000。区間サイズ)

 いもす法  区間に加算がO( N * 1 )   、最大値クエリ:O(M)

f:id:kuuso1:20140916003903p:image

コードは以下

using System;
using System.Collections;
using System.Collections.Generic;
 
class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		int N=ri();
		SegTreeA STa=new SegTreeA(1000001);
		for(int i=0;i<N;i++){
			var d=ria();
			STa.Add(d[0],d[1]+1,1,0,0,1000001);
		}
		int ans=STa.CallMax();
		Console.WriteLine(ans);
	}

	public Sol(){
	}

	static int ri(){return int.Parse(Console.ReadLine());}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
}

class SegTreeA{
	/* 変数名が不適切ですorz
	  Data[]:遅延評価用のバッファ 上図の青のノード
	  ALL[] :真値用のバッファ   上図の緑のノード 
	      今回はクエリが1回なので、CallMax関数内変数として割り当てています */


	//segment Tree 
	// 0-origin
	protected int[] Data;	//実体
	protected int N;		//size 
	protected int n;		//size (2の冪)
	
	//コンストラクタ
	public SegTreeA(int n_){
		N=n_;
		n=1;
		while(n<n_)n*=2;
		Data=new int[2*n-1];
		for(int i=0;i<2*n-1;i++)Data[i]=0;
	}
	
	public void Add(int a,int b,int val,int k,int l,int r){
		// [a,b) ⊃ [l,r) ⇒Data[k]に+val
		if(a<=l && r<=b){
			Data[k]+=val;
		}else if( (l<b) && (a<r) ){
			Add(a,b,val,k*2+1,l,(l+r)/2);
			Add(a,b,val,k*2+2,(l+r)/2,r);
		}
	}
	
	public int CallMax(){
		int[] All=new int[2*n-1];
		for(int i=n-1;i<2*n-1;i++)All[i]=Data[i];
		for(int i=n-2;i>=0;i--){
			All[i]=Data[i]+Math.Max(All[i*2+1],All[i*2+2]);
		}
		return All[0];
	}
}

本当はツリーのアップデートも根側から葉側に実施してからRMQする方がいいですが、今回はクエリ1回なので適当です。

アップデートのタイミングと遅延評価の表現とを考えるといろいろ考えることやできそうなことが多そうで、

実際セグメントツリー関連は@kyuridenamidaさんの記事@kagamizさんの記事@iwiiwさんのスライドや蟻本など、いろいろ参考になる/読み応えのある記事が多いので精進したいです。

ともあれ個人的に今回遅延評価の感触(の触り)がつかめたので満足。あとABC014はいもす法(C問題)・LCA(D問題)と非常に教育的でビギナーの僕には大変ためになる回でした。