Hatena::Grouptopcoder

kuuso1の日記

2014-10-27

CodeForces #275 div1 B. Interesting Array

| 23:49 | CodeForces #275 div1 B. Interesting Array - kuuso1の日記 を含むブックマーク はてなブックマーク - CodeForces #275 div1 B. Interesting Array - kuuso1の日記

http://codeforces.com/contest/482/problem/B

  • 数列 A[n](n=1 to N) について、M個の条件が与えられる
  • 条件は l_i, r_i, q_i の形で与えられ、これは A[ l_i ] & A[ l_i + 1 ] &...& A[ r_i ] == q_i を意味する.ここで & は論理積を表す
  • これらの条件をすべて満たす A[n] が存在するなら "YES" に続けてその一例を列挙する.存在しなければ "NO" を返す.

(制約)1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^5, 1 ≤ l_i ≤ r_i ≤ N, q_i < 2^30

方針:それぞれの制約を満たすためには、少なくとも区間 [ l_i, r_i ]の全てに q_i の1ビットが立っていなければならない。

・q_iの0ビットは、[ l_i, r_i ] の中に1つでも0が立っていればよいが、それが他の制約によって満たされない状況かどうかを判定すればよい。

・遅延セグメントツリーで、全ての区間 [ l_i, r_i ] について q_i の1ビットを有効にする。論理和でどんどん足していく。

・その後、実際に全ての区間 [ l_i, r_i ] について論理積をとり、 q_i に等しいかを確認する。全てを満たすなら葉を書き出せばよい。

計算量: 遅延和でO(MlogN)、遅延更新にO(N)、論理積クエリでO(MlogN)

★反省など

本番中にかなりエンバグしてしまい結局通せなかったので反省を込めて作図。

遅延ノードは根から葉へ向けて更新すればよいが、クエリをO(logN)で実施できるのは、真値用ノードが常に葉の計算結果をもっているからなので

それを忘れては本末転倒である。。

f:id:kuuso1:20141027232936p: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(){
		
		SegTreeA ST =new SegTreeA(N);
		
		for(int i=0;i<M;i++){
			ST.Add(L[i][0]-1,L[i][1],L[i][2],0,0,ST.n);
		}
		ST.AllUpdate();
//ST.Dump();		
		
		for(int i=0;i<M;i++){
			if(L[i][2]!=ST.Query(L[i][0]-1,L[i][1],0,0,ST.n)){
				Console.WriteLine("NO");
				return;
			}
		}
		
		Console.WriteLine("YES");
		ST.Bump();
		
	}
	List<int[]> L;
	int N;
	int M;
	public Sol(){
		var d=ria();
		N=d[0];M=d[1];
		L=new List<int[]>();
		for(int i=0;i<M;i++){
			L.Add(ria());
		}
	}

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



class SegTreeA{

	//segment Tree 
	// 0-origin
	int[] LData;		//遅延
	int[] Data;		//実体
	int N;			//size 
	public int n;		//size (2の冪)
	
	//コンストラクタ
	public SegTreeA(int n_){
		N=n_;
		n=1;
		while(n<n_)n*=2;
		LData=new int[2*n-1];
		Data=new int[2*n-1];
	}
	
	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){
			LData[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 void AllUpdate(){
		//n=4	   0
		//	 1   2
		//	3 4 5 6
		
		//まず遅延成分を最下部まで伝播
		for(int i=0;i<n-1;i++){
			LData[i*2+1]|=LData[i];
			LData[i*2+2]|=LData[i];
			LData[i]=0;//遅延バッファを空に
		}
		
		//最下部に加える
		for(int i=n-1;i<2*n-1;i++){
			Data[i]|=LData[i];
			LData[i]=0;//遅延バッファを空に
		}
		
		//ANDでクエリをとるので、無効セルは111…で塗りつぶしておく
		for(int i=n-1+N;i<2*n-1;i++)Data[i]=(1<<30) -1;
		
		//クエリ用にノードを最下部から根の方向へUpdate
		for(int i=n-2;i>=0;i--){
			Data[i]=Data[2*i+1]&Data[2*i+2];
		}
	}
	
	
	//	外から呼ぶ時は Query(a,b,0,0,n) の形で呼ぶ
	public int Query(int a,int b,int k,int l,int r){
		// [a,b) ∩ [l,r) =φ ⇒Infを返す
		if(r<=a || b<=l) return (1<<30) -1;

		// [a,b) ⊃ [l,r) ⇒Data[k]を返す 
		if(a<=l && r<=b)return Data[k];
		// さもなくば、両手のANDを返す
		int vl=Query(a,b,k*2+1,l,(l+r)/2);
		int vr=Query(a,b,k*2+2,(l+r)/2,r);
		return vl&vr;
	}
	public void Bump(){
		for(int i=n-1;i<n-1+N;i++){
			Console.Write(i==n-1?"{0}":" {0}",Data[i]);
		}
		Console.WriteLine();
	}
	
	public void Dump(){
		//デバッグ用。ツリー状にprint
		Console.WriteLine();
		int h=0;
		int cnt=0;
		for(int i=0;i<Data.Length;i++){
			Console.Write("{0} ",Data[i]);
			cnt++;
			if(cnt==1<<h){
				cnt=0;
				h++;
				Console.WriteLine();
			}
		}
		Console.WriteLine();
		h=0;
		cnt=0;
		for(int i=0;i<Data.Length;i++){
			Console.Write("{0} ",LData[i]);
			cnt++;
			if(cnt==1<<h){
				cnt=0;
				h++;
				Console.WriteLine();
			}
		}
	}
	
}

・遅延評価部分は今の僕のスキルだとO(N)で更新するしかないので、クエリと遅延評価が交互に来るようなものでは使えないですが、

 「セグメント木を弄れば解ける!」と思った問題でエンバグしない程度には慣れたいものです。

 (まぁ、今回エンバグしてBを通せずdiv2落ちしたのですがorz