CSAcademy Round #41 : F. Subset Trees

Eよりこっちの方が簡単では？
https://csacademy.com/contest/round-41/task/subset-trees/

問題

数直線上でN個のセグメント[L[i],R[i]]が与えられる。
これらのセグメントの部分集合のうち、以下を満たすものを求めよ。

• セグメントを頂点とみなしたグラフを考える。
• ２つのセグメントが共通部分を持つなら両者に辺を張る。
• これらの辺により頂点が木を成す。

解法

木を成すの条件より、あるX座標をカバーするセグメントは最大2つである。
セグメントをL[i]の昇順に並べ、以下を順次求めよう。

dp(i,x,y) := 0～i番目のセグメントの部分集合のうち、選んだ要素vにおけるR[v]の最大値がyで、2つ以上のセグメントの共通部分の最大値がxであるようなものの組み合わせ。

(i+1)番目のセグメントを配置するとき、以下の２通りが考えられる。

• (i+1)番目のセグメントが最初のセグメントとなる。この時dp(i+1,L[i+1],R[i+1]) += 1
• x＜L[i+1]≦yであるような状態に対し[L[i+1],R[i+1]]を付与することができる。
  • y＜R[i+1]ならdp(i,y,R[i+1]) += dp(i,x,y)
  • y≧R[i+1]ならdp(i,R[i+1],y) += dp(i,x,y)

上記処理を愚直に行うとO(N^3)かかるが、ほとんど似た形の累積和で構成されるので、BIT等使うとO(N^2*logN)に落とせる。
他にもO(N^2)解法もあるようだ。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	V set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};


int N,M;
int H[101010],C[101010];
BIT<int,20> bt;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	FOR(i,N) cin>>H[i];
	sort(H,H+N);
	bt.add(0,H[0]);
	for(i=1;i<N;i++) bt.add(i,H[i]-H[i-1]);
	bt.add(N,201010);
	
	FOR(i,M) {
		cin>>C[i];
		if(C[i]>N) break;
		y=N-C[i];
		x = bt.total(y);
		if(x<=0) break;
		
		x=bt.lower_bound(bt.total(y));
		k=bt.lower_bound(bt.total(y)+1);
		bt.add(k,-1);
		bt.add(x,-1);
		bt.add(x+(k-y),1);
	}
	
	cout<<i<<endl;
	
	
}

まとめ

こっちがEでもいいと思うけどな。