101 Hack 45 : E. Distant Pairs

うまくSegTreeに落とせなかった。
https://www.hackerrank.com/contests/101hack45/challenges/distant-pairs

問題

円周上に0～(C-1)のC個の座標が順に並んでいる。
ここで点のペアをN組考える。各ペアは、2つの座標(A[i],B[i])からなる。

さらにこのペアを2つ組み合わせたときの距離を、2つのペア中に含まれる4頂点におけるもっとも近い2点の距離とする。

与えられたN組のペアから2組選んで得られる距離の最大値を求めよ。

解法

距離dを二分探索で求めよう。
まずA[i],B[i]間の距離がd未満のものは無駄なので相手にしない。

よってA[i]+d＜B[i]とする。
各点をA[i]の小さい順に処理していこう。

今(A[i],B[i])を処理するとき、j＜iとなるペアj,iが距離d以上となるかどうかを判定する。
そのためには(A[j],B[j])と(A[i],B[i])は以下を満たさなければならない。

• A[j] ≦ A[i]-d
• B[j]は[max(0, B[i]+d-L), A[i]-d], [A[i]+d, B[i]-d]、[B[i]+d, min(C-1, A[i]-d-1+L)]のいずれかの区間に含まれていなければならない。

逆に考えると、[max(0, B[j]+d-L), A[i]-d], [A[i]+d, B[i]-d]、[B[i]+d, min(C-1, A[j]-d-1+L)]にB[j]があるようなもののうち、B[j]+d-C≦A[j]≦A[i]-dであるA[j]が見つかればよい。
前者の判定は難しいが、後者はRange Maximum Queryを用いてだいぶ容易に解くことができる。
(A[i],B[i])を処理する際、尺取り法の要領でA[j] ≦ A[i]-dを満たすjをRMQのデータ構造に追加していく。
その際、B[j]に対応する座標に値A[j]を登録して最大値を更新しよう。

あとはRMQで3つの区間[max(0, B[i]+d-L), A[i]-d], [A[i]+d, B[i]-d]、[B[i]+d, min(C-1, A[i]-d-1+L)]を探し、B[j]+d-C≦A[j]を満たすA[j]が素材すれば、距離d以上を満たすペアの対が存在する。

int C;
int N;
pair<int,int> P[101010];
int A[101010],B[101010],S[101010];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-1<<20;
	V comp(V l,V r){ return max(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 ok(int d) {
	int i,ptr;
	
	SegTree_1<int,1<<20> st;
	
	ptr=0;
	FOR(i,N) {
		if(S[i]<d) continue;
		while(A[i]>=A[ptr]+d) {
			if(S[ptr]>=d) st.update(B[ptr],A[ptr]);
			ptr++;
		}
		
		int ma = st.getval(max(0,B[i]+d-C), A[i]-d+1);
		ma=max(ma, st.getval(A[i]+d, B[i]-d+1));
		ma=max(ma, st.getval(B[i]+d, min(C,A[i]-d+C+1)));
		if(ma>=0 && ma+C >= B[i]+d) return 1;
	}
	return 0;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C;
	FOR(i,N) {
		cin>>P[i].first>>P[i].second;
		if(P[i].second<P[i].first) swap(P[i].first,P[i].second);
	}
	
	sort(P,P+N);
	FOR(i,N) {
		A[i]=P[i].first;
		B[i]=P[i].second;
		S[i]=min(B[i]-A[i],C-(B[i]-A[i]));
	}
	
	int ret=0;
	for(i=20;i>=0;i--) if(ok(ret+(1<<i))) ret+=1<<i;
	cout<<ret<<endl;
	
}

まとめ

これは思いつかんな…。