luogu2093 [国家集训队]JZPFAR

题面不符？……
#include <algorithm>

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

int n, m, nowD, rot, din, kk;

const ll oo=9e18;

struct Point{

	int d[2], mn[2], mx[2], id, idmin, l, r;

	int & operator[](int x){

		return d[x];

	}

	bool operator<(const Point &x)const{

		return d[nowD]<x.d[nowD];

	}

}p[100005], T;

struct QueryNode{

	int idx;

	ll dis;

	QueryNode(int id=0, ll di=0){

		idx = id;

		dis = di;

	}

}qn[25];

bool cmp(const QueryNode &x, const QueryNode &y){

	if(x.dis!=y.dis)	return x.dis>y.dis;

	return x.idx<y.idx;

}

struct KDTree{

	Point t[100005];

	void pushUp(int k){

		int l=t[k].l, r=t[k].r;

		t[k].idmin = t[k].id;

		if(l)	t[k].idmin = t[l].idmin;

		if(r)	t[k].idmin = t[r].idmin;

		for(int i=0; i<2; i++){

			t[k].mn[i] = t[k].mx[i] = t[k][i];

			if(l){

				t[k].mn[i] = min(t[k].mn[i], t[l].mn[i]);

				t[k].mx[i] = max(t[k].mx[i], t[l].mx[i]);

			}

			if(r){

				t[k].mn[i] = min(t[k].mn[i], t[r].mn[i]);

				t[k].mx[i] = max(t[k].mx[i], t[r].mx[i]);

			}

		}

	}

	int build(int l, int r, int now){

		nowD = now;

		int mid=(l+r)>>1;

		nth_element(p+l, p+mid, p+r+1);

		t[mid] = p[mid];

		if(l<mid)	t[mid].l = build(l, mid-1, now^1);

		if(mid<r)	t[mid].r = build(mid+1, r, now^1);

		pushUp(mid);

		return mid;

	}

	ll getDis(const Point &u, const Point &v){

		return (ll)(u.d[0]-v.d[0])*(u.d[0]-v.d[0])+(ll)(u.d[1]-v.d[1])*(u.d[1]-v.d[1]);

	}

	ll calc(int x){

		ll re=0;

		for(int i=0; i<2; i++){

			ll tmp=max(abs(t[x].mn[i]-T[i]), abs(t[x].mx[i]-T[i]));

			re += tmp * tmp;

		}

		return re;

	}

	void query(int k){

		int l=t[k].l, r=t[k].r;

		ll dis=getDis(t[k], T), disl=-oo, disr=-oo;

		if(dis>qn[1].dis || (dis==qn[1].dis && t[k].id<qn[1].idx)){

			pop_heap(qn+1, qn+1+din, cmp);

			qn[din] = QueryNode(t[k].id, dis);

			// cout<<t[k].id<<" as t[k].id\n";

			push_heap(qn+1, qn+1+din, cmp);

		}

		if(l)	disl = calc(l);

		if(r)	disr = calc(r);

		if(disl>disr){

			if(disl>qn[1].dis || (disl==qn[1].dis && t[l].idmin<qn[1].idx))

				query(l);

			if(disr>qn[1].dis || (disr==qn[1].dis && t[r].idmin<qn[1].idx))

				query(r);

		}

		else{

			if(disr>qn[1].dis || (disr==qn[1].dis && t[r].idmin<qn[1].idx))

				query(r);

			if(disl>qn[1].dis || (disl==qn[1].dis && t[l].idmin<qn[1].idx))

				query(l);

		}

	}

}kdt;

int main(){

	cin>>n;

	for(int i=1; i<=n; i++){

		scanf("%d %d", &p[i][0], &p[i][1]);

		p[i].id = p[i].idmin = i;

	}

	rot = kdt.build(1, n, 0);

	cin>>m;

	while(m--){

		din = 0;

		scanf("%d %d %d", &T[0], &T[1], &kk);

		while(kk--)	qn[++din] = QueryNode(0, -oo);

		kdt.query(rot);

		// while(din){

		// 	// cout<<qn[1].dis<<" "<<qn[1].idx<<" as dis&idx\n";

		// 	pop_heap(qn+1, qn+1+din, cmp);

		// 	din--;

		// }

		printf("%d\n", qn[1].idx);

	}

	return 0;

}
巴特西

luogu2093 [国家集训队]JZPFAR

最新文章

热门文章
