Codeforces #238 Div1 D. Hill Climbing

convex hull trickが身についてなくて最後まで詰められなかった問題。
http://codeforces.com/contest/406/problem/D

問題

1～N番の山があり、それぞれは位置X[i]にあり、高さはY[i]である。
ここでM個の以下のクエリに答えよ。

• 数値a,bが与えられるので、その番号に対応する山に2人の人がいるとする。
• 以下のように移動するとき、2人の合流地点を答えよ。
  • そこで待っていればもう一人が来るのであれば、それ以上移動しない。
  • そうでない場合、今いるより右側の山のうち(他の山に邪魔されず直線的に移動できる)最も遠くの山頂に移動する。

解法

まず、各山にいる人が1手でどこに移動するかを求める。
愚直に行うとO(N^2)かかるが、ここはconvex hull trickを用いることでO(N)で求めることができる。

そこまでできれば、各クエリにおいて後はN番の山をrootとした木におけるLowest Common Ancestorを求めるだけである。
よって事前のdoublingがO(N logN)、クエリ処理はO(M logN)で合わせてO((N+M)logN)で処理可能。

int N;
ll X[100001],Y[100001];
int depth[100001];
int Q;

int tar[21][1<<20];

int proc(int y,int step) {
	int i;
	FOR(i,20) if(step&(1<<i)) y=tar[i][y];
	return y;
}

int dist(int x,int y) {
	int res=0,i;
	if(depth[x]<depth[y]) swap(x,y);
	x=proc(x,depth[x]-depth[y]);
	if(x==y) return x;
	int mi=N-1;
	for(i=19;i>=0;i--) {
		if(tar[i][x]==tar[i][y]) mi=min(mi,tar[i][x]);
		if(tar[i][x]!=tar[i][y]) x=tar[i][x],y=tar[i][y];
	}
	
	return mi;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	int xx;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(i,N) tar[0][i]=i+1;
	tar[0][N-1]=N-1;
	vector<int> V;
	V.push_back(N-1);
	for(i=N-2;i>=0;i--) {
		while(V.size()>=2) {
			int j=V[V.size()-1],k=V[V.size()-2];
			if((X[j]-X[i])*(Y[k]-Y[i])<=(X[k]-X[i])*(Y[j]-Y[i])) break;
			V.pop_back();
		}
		tar[0][i]=V[V.size()-1];
		V.push_back(i);
		
	}
	FOR(x,20) {
		FOR(i,N) tar[x+1][i]=tar[x][tar[x][i]];
	}
	for(i=N-2;i>=0;i--) depth[i]=depth[tar[0][i]]+1;
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		_P("%d ",dist(x-1,y-1)+1);
	}
	_P("\n");
}

まとめ

本番、Doubling+LCAを使うことはわかったが、Convex hull trickを実装しようとしている間に時間切れ。
これ苦手なので練習しておきたいな…。