Codeforces #165 div1-D Maximum Waterfall

http://www.codeforces.com/contest/269/problem/D

問題概要

高さ、左端、右端の決まった棚がN個ある。
i番目の棚の高さ、左端、右端をそれぞれhi,li,riとおく。

ある棚iから、ある棚jに水を流せる時、

• max(li,lj)＜min(ri,rj) つまり棚iと棚jが上から見た時重なっていて、
• hj＜hi で
• 棚iから棚kに水を流せて、棚kから棚jへ水を流せるようなkが存在しない

という3つが満たされている。

ある棚iからある棚jに水を流すとき、流せる量は、min(ri,rj)-max(li,lj)

最も上の長さが無限の棚から、最も下の長さが無限の棚に、なるべく多く一本の水を流したい
水を流す経路の流量は、棚から棚へ流せる水の量の最小値

流せる水の最大値を求めよ

N<=10^5
|li,ri|<=10^9
hi<=10^9

方針

左右の座標の値をまずは圧縮

棚を下から順番に見ていく
dp[i]:=棚iから水を流すときの流せる水の最大値

棚iの範囲で、棚iより下の棚たちを見下ろした時に見える棚(棚jとおく)すべてについて、
棚jに棚iから水を下ろせるか考える。

棚jに水を下ろせるのは、棚iの範囲とかぶっている棚jの範囲がすべて見えるとき
この時、dp[i]=max(dp[i],min(dp[j],(iとjの被っている部分の長さ)))
と更新できる。

更新が終わったら、上から見た時に見える棚に棚iを追加する
上から見た時に見える棚の管理には、set＜pair＜int,int> >などを使えばできる

dp[最も上の棚の番号] が答え

棚iから下へ見える棚は最大N個有りそうなので、O(N^2)かO(N^2logN)のような気がするが、
もしある区間を見下ろせたなら、その区間はiによって覆われるので棚iによってしか見下ろされない
更新が終わると、棚iの区間、棚iの両側にもともとあり、途切れることとなった区間 の3つが追加される

区間は1回しか見下ろされないので、O(N * logN)ぐらいで終了する。

下のコードのdoitは、上の方針と少し違い、
[l,r)の範囲で最も上にある区間をセグメント木により探し、その区間で更新できるか調べ、
最も上にある区間以外の残りの範囲について再帰的に調べています

実装量は多いですが挿入削除の面倒なことが少ないかと思います

using namespace std;
static const int INF =1000000005;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef long long int lint;
typedef pair<int,int> pi;
struct segtree{
	int val[800005],all[800005];
	int n;
	void init(int n_){
		n=1;
		while(n<n_) n<<=1;
		for(int i=0;i<n*2;++i) val[i]=-1,all[i]=-1;
	}
	int query(int a,int b,int i,int l,int r){
		if(a<=l && r<=b) return val[i];
		if(b<=l || r<=a) return -1;
		int md=(l+r)>>1;
		if(all[i]!=-1){
			all[i*2+1]=all[i*2+2]=val[i*2+1]=val[i*2+2]=all[i];
			all[i]=-1;
		}
		return max(query(a,b,i*2+1,l,md),query(a,b,i*2+2,md,r));
	}
	void set(int a,int b,int i,int l,int r,int v){
		if(a<=l && r<=b){
			val[i]=v;
			all[i]=v;
			return;
		}
		if(b<=l || r<=a) return;
		int md=(l+r)>>1;
		if(all[i]!=-1){
			all[i*2+1]=all[i*2+2]=val[i*2+1]=val[i*2+2]=all[i];
			all[i]=-1;
		}
		set(a,b,i*2+1,l,md,v);
		set(a,b,i*2+2,md,r,v);
		val[i]=max(val[i*2+1],val[i*2+2]);
	}
};
segtree seg;
pair<int,pi> wall[100005];
int zip[200005];
int n,t;
int dp[100005];

void doit(int l,int r,int who,int excL=1,int excR=1){
//excL/excR 左/右に伸びていてよいかどうか(1ならOK)
	int id=seg.query(l,r,0,0,seg.n);
	if(id==-1){//最も下の棚専用
		seg.set(l,r,0,0,seg.n,who);
		dp[who]=zip[r]-zip[l];
		return;
	}
	int l2=wall[id].second.first,r2=wall[id].second.second;
	if(!(l2<l && excL==0) && !(r<r2 && excR==0)){
		dp[who]=max(dp[who],min(dp[id],min(zip[r],zip[r2])-max(zip[l],zip[l2])));
	}

	if(l<l2) doit(l,l2,who,excL,0);
	if(r2<r) doit(r2,r,who,0,excR);
}

int main(){
	scanf("%d%d",&n,&t);
	for(int i=0;i<n;++i){
		int a,b,h;scanf("%d%d%d",&h,&a,&b);
		zip[i*2]=a;
		zip[i*2+1]=b;
		wall[i]=make_pair(h,make_pair(a,b));
	}

	zip[n*2]=-INF;
	zip[n*2+1]=INF;
	sort(zip,zip+n*2+2);
	int zn=unique(zip,zip+n*2+2)-zip;
	wall[n++]=make_pair(0,make_pair(-INF,INF));
	wall[n++]=make_pair(t,make_pair(-INF,INF));
	for(int i=0;i<n;++i){
		wall[i].second.first=lower_bound(zip,zip+zn,wall[i].second.first)-zip;
		wall[i].second.second=lower_bound(zip,zip+zn,wall[i].second.second)-zip;
	}
	sort(wall,wall+n);

	seg.init(zn);
	for(int i=0;i<n;++i){
		int h=wall[i].first,l=wall[i].second.first,r=wall[i].second.second;

		doit(l,r,i);
		seg.set(l,r,0,0,seg.n,i);
	}
	printf("%d\n",dp[n-1]);


	return 0;
}