Codeforces #772 : Div2 F. Closest Pair

本番解いておきたかった。
https://codeforces.com/contest/1635/problem/F

問題

1次元座標上に、N個の重み付きの点が与えられる。
i番目の点は、座標X(i)、重みW(i)である。また、座標は昇順である。
点iと点jの距離を、|X(i)-X(j)|*(W(i)+W(j))で定義するものとする。

以下のクエリに答えよ。

• X座標の範囲が与えられる。範囲内の異なる２点の対のうち、上記距離の最小値を求めよ。

解法

各点iに対し、W(i)以下の重みをもつ最寄りの点を、左右それぞれL(i)及びR(i)とする。
その場合、解の候補は各iに対し(L(i),i)の対と(i,R(i))のいずれかで計2N通りである。

これがわかれば、後は平面走査の要領で区間最小値を取るSegTreeで処理できる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=4LL<<60;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int N,Q;
ll X[303030],W[303030];
SegTree_1<ll,1<<20> st;
vector<int> add[303030];
int L[303030],R[303030];
vector<int> qu[303030];
ll ret[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&Q);
	vector<pair<int,int>> V={{0,0}};
	for(i=1;i<=N;i++) {
		scanf("%d%d",&x,&y);
		X[i]=x+(1000000003);
		W[i]=y;
		while(V.back().first>y) V.pop_back();
		if(V.back().second!=0) add[V.back().second].push_back(i);
		V.push_back({W[i],i});
	}
	V={{0,N+1}};
	for(i=N;i>=1;i--) {
		while(V.back().first>W[i]) V.pop_back();
		if(V.back().second!=N+1) add[i].push_back(V.back().second);
		V.push_back({W[i],i});
	}
	FOR(i,Q) {
		scanf("%d%d",&L[i],&R[i]);
		R[i]++;
		qu[L[i]].push_back(i);
	}
	
	for(i=N;i>=1;i--) {
		FORR(e,add[i]) st.update(e,1LL*(X[e]-X[i])*(W[e]+W[i]));
		FORR(a,qu[i]) ret[a]=st.getval(i,R[a]);
	}
	FOR(i,Q) cout<<ret[i]<<endl;
		
		
}

まとめ

考察の初手にたどり着けるかが重要。