[国家集训队]JZPFAR

嘟嘟嘟

k-d tree模板之二：查询第k大距离。（所以是怎么上黑的）

因为k-d tree的查询就是暴力嘛，所以我就想到了一个很暴力的做法：每一次查询用一个长度为k的优先队列维护。按距离递增，编号递减的方式排序。

然后查询的时候，如果队列长度大于k了，就尝试用当前节点更新队首。

刚开始没看到k的范围只有20，以为也是1e5，所以觉得这方法不行，最后还是看了题解……

结果题解做法和我几乎一样，只不过有点优化：

1.先往队列里放入k个极小值，就能避免队空以及判断长度等问题。

2.查询的时候优先往估价函数大的子树查询，这样这个子树查完后可能就不会进入估价函数小的兄弟了。

3.对了，这里的估价函数是最长距离。

然后我自认为我的查询代码比题解简单：固定往左子树找，如果左子树估价函数小于右子树，就交换左右子树。这样是没有影响的，还避免了复杂的分类讨论。

k-d tree debug也特别简单，直接改成爆搜，就知道是建树错了还是查询错了。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<ctime>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define In inline

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 1e5 + 5;

inline ll read()

{

	ll ans = 0;

	char ch = getchar(), last = ' ';

	while(!isdigit(ch)) last = ch, ch = getchar();

	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

	if(last == '-') ans = -ans;

	return ans;

}

inline void write(ll x)

{

	if(x < 0) x = -x, putchar('-');

	if(x >= 10) write(x / 10);

	putchar(x % 10 + '0');

}

int n, m, Dim;

struct Tree

{

	int ch[2], id;

	ll d[2], Min[2], Max[2];

	In bool operator < (const Tree& oth)const

	{

		return d[Dim] < oth.d[Dim];

	}

}t[maxn << 2], a[maxn];

int root, tcnt = 0;

In void pushup(int now)

{

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

	{

		if(t[now].ch[0])

		{

			t[now].Min[i] = min(t[now].Min[i], t[t[now].ch[0]].Min[i]);

			t[now].Max[i] = max(t[now].Max[i], t[t[now].ch[0]].Max[i]);

		}

		if(t[now].ch[1])

		{

			t[now].Min[i] = min(t[now].Min[i], t[t[now].ch[1]].Min[i]);

			t[now].Max[i] = max(t[now].Max[i], t[t[now].ch[1]].Max[i]);

		}

	}

}

In void build(int& now, int L, int R, int d)

{

	if(L > R) return;

	int mid = (L + R) >> 1;

	Dim = d;

	nth_element(a + L, a + mid, a + R + 1);

	t[now = ++tcnt] = a[mid];

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

	{

		t[now].ch[i] = 0;

		t[now].Min[i] = t[now].Max[i] = t[now].d[i];

	}

	build(t[now].ch[0], L, mid - 1, d ^ 1);

	build(t[now].ch[1], mid + 1, R, d ^ 1);

	pushup(now);

}

struct Node

{

	ll dis; int id;

	In bool operator < (const Node& oth)const

	{

		return dis > oth.dis || (dis == oth.dis && id < oth.id);

	}

};

priority_queue<Node> q;

In ll dis(int now, ll* d)

{

	ll ret = 0;

	for(int i = 0; i < 2; ++i) ret += (t[now].d[i] - d[i]) * (t[now].d[i] - d[i]);

	return ret;

}

In ll price(int now, ll* d)

{

	ll ret = 0;

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

	{

		ll Max = max(abs(t[now].Max[i] - d[i]), abs(t[now].Min[i] - d[i]));

		ret += Max * Max;

	}

	return ret;

}

In void query(int now, ll* d)

{

	if(!now) return;

	ll tp = dis(now, d);

	if(tp > q.top().dis || (tp == q.top().dis && t[now].id < q.top().id)) q.pop(), q.push((Node){tp, t[now].id});

	ll disL = price(t[now].ch[0], d), disR = price(t[now].ch[1], d);

	if(disL < disR) swap(t[now].ch[0], t[now].ch[1]), swap(disL, disR);

	if(disL > q.top().dis || (disL == q.top().dis && t[t[now].ch[0]].id < q.top().id)) query(t[now].ch[0], d);

	if(disR > q.top().dis || (disR == q.top().dis && t[t[now].ch[1]].id < q.top().id)) query(t[now].ch[1], d);

}

int main()

{

	n = read();

	for(int i = 1; i <= n; ++i) a[i].d[0] = read(), a[i].d[1] = read(), a[i].id = i;

	build(root, 1, n, 0);

	m = read();

	for(int i = 1; i <= m; ++i)

	{

		static ll d[2];

		d[0] = read(), d[1] = read(); int k = read();

		while(!q.empty()) q.pop();

		for(int j = 1; j <= k; ++j) q.push((Node){-1, 0});

		query(root, d);

		write(q.top().id), enter;

	}

	return 0;

}

巴特西

[国家集训队]JZPFAR

最新文章

热门文章