AtCoder ABC #233 : Ex - Manhattan Christmas Tree

HじゃなくExになったか。
https://atcoder.jp/contests/abc233/tasks/abc233_h

問題

2次元座標上にN個の格子点の座標が指定される。
以下のクエリに答えよ。

• 座標(a,b)から見て、マンハッタン距離がK番目に近い格子点までの距離は？

解法

まずはマンハッタン距離に関する典型テクとして、格子点やクエリの座標を
X'=X-Y
Y'=X+Y
のように座標変換しておこう。
以下、登場する座標は変換済みの座標で考える。

すると、X座標が[a-R,a+R]、Y座標が[b-R,b+R]の範囲に、格子点がK個以上入るような最小のRを求める問題になる。
これは、SegTreeでX座標毎にY座標の集合を持ち、「X座標の区間[a-R,a+R]内にあるY座標(b+R)以下及び(b-R-1)以下の要素数」を高速に数え上げられれば、二分探索で求められる。

int N;
int X[101010],Y[101010];

template<class V,int NV> class SegTree_1 {
public:
	vector<vector<V>> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val.resize(NV*2);};
	V getval(int x,int y,V v,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return 0;
		if(x<=l && r<=y) {
			return lower_bound(ALL(val[k]),v+1)-val[k].begin();
		}
		return getval(x,y,v,l,(l+r)/2,k*2)+getval(x,y,v,(l+r)/2,r,k*2+1);
	}
	void set(int entry,V v) {
		val[entry+NV].push_back(v);
	}
	void build() {
		for(int i=2*NV-1;i>=NV;i--) sort(ALL(val[i]));
		for(int i=NV-1;i>=1;i--) {
			val[i].clear();
			int a=0,b=0;
			int x=i*2,y=i*2+1;
			while(a<val[x].size() || b<val[y].size()) {
				if(a==val[x].size()) {
					val[i].push_back(val[y][b++]);
				}
				else if(b==val[y].size()) {
					val[i].push_back(val[x][a++]);
				}
				else if(val[x][a]<val[y][b]) {
					val[i].push_back(val[x][a++]);
				}
				else {
					val[i].push_back(val[y][b++]);
				}
			}
		}
	}
};
SegTree_1<int,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		X[i]=x-y+100000;
		Y[i]=x+y+100000;
		st.set(X[i],Y[i]);
	}
	st.build();
	int Q;
	int A,B,K;
	cin>>Q;
	while(Q--) {
		cin>>x>>y>>K;
		A=x-y+100000;
		B=x+y+100000;
		
		int ret=(1<<19)-1;
		for(i=18;i>=0;i--) {
			int tmp=ret-(1<<i);
			ll a=st.getval(A-tmp,A+tmp+1,B+tmp);
			ll b=st.getval(A-tmp,A+tmp+1,B-tmp-1);
			if(a-b>=K) ret=tmp;
		}
		cout<<ret<<endl;
		
	}
	
	
		
}

まとめ

HardとExtra、どっちが難しいんだろうね(何が)。