洛谷 P4475 巧克力王国 kd树

缘起

继续学习kd树~ 洛谷 P4475 巧克力王国

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
题目描述
巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜欢
过于甜的巧克力。

对于每一块巧克力，我们设 x 和 y 为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的评判标准，所
以每个人都有两个参数 a 和 b ，分别为他自己为牛奶和可可定义的权重， 因此牛奶和可可含量分别为 x 和 
y 的巧克力对于他的甜味程度即为 ax+by。而每个人又有一个甜味限度 cc ，所有甜味程度大于等于 c 
的巧克力他都无法接受。每块巧克力都有一个美味值 h 。

现在我们想知道对于每个人，他所能接受的巧克力的美味值之和为多少。

输入格式
第一行两个正整数 n 和 m ，分别表示巧克力个数和询问个数。
接下来n行，每行三个整数 x , y , h ，含义如题目所示。
再接下来 m 行，每行三个整数 a , b , c ，含义如题目所示。

输出格式
输出m行，其中第i行表示第i个人所能接受的巧克力的美味值之和。

输入输出样例
输入 #1复制
3 3
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7
输出 #1复制
5
0
4
说明/提示
对于100%的数据，1<=n,m<=50000,-10^9<=a_i,b_i,x_i,y_i<=10^9

本题其实和【1】很类似，都是kd树节点上维护某些东西. 其实是我想复杂了，本题其实没有太多几何学的东西的(唉，害得我一开始陷入了几何学美感的迷思~). 只有暴力. 和【1】一样, 对所有巧克力建kd树, 树上每个节点维护它所在子树上平面上的最远范围——mi[0,1]和mx[0,1], 这一点和【1】是完全一样. 但是不一样的地方在于，它并不像【1】那样是求某种极值（【1】是求最远距离），而是树上节点的某种属性的和（即本题中的h值）. 所以本题的kd树上的节点还需要维护一个属性h表示它所在的子树上的所有节点的h值的和.

咳咳咳~ 其实本题的套路和【1】一模一样~ 就是遍历每个人, 将每个人打进巧克力建的kd树中, 然后在kd树上搜索, 树上搜索为什么比直接对每个人暴力遍历所有的巧克力好? 因为如果这个人和该树根节点的mi、mx计算ax+by最大值<=c或者最小值>=c的话（和【1】类似的，这就是搜索的启发式函数）则整个树上的节点都会满足ax+by<=c或者>=c, 则我们就不必傻傻的去遍历这棵子树中每一个节点了. 而是直接加上去或者整棵子树被pass掉.

数据依旧是同样的数据，但是因为组织形式的不同（线性表变成了kd树），遍历的复杂度就完全不一样了，这不就是数据结构和算法的魅力吗?

所以有了【1】的基础, 就容易写出下面的代码了（代码很多地方没写注释, 不懂的话，看【1】）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long LL;
//#define LOCAL
int n,m, depth;
const int maxn = 50005,k=2;	

struct KdTreeNode
{
	LL x[2];
	LL mi[2], mx[2], h, sum; // h是自己的h(即巧克力自己的h),sum是子树的节点的h的和
	bool flag;
	bool operator <(const KdTreeNode &o) const
	{
		return x[depth]<o.x[depth];
	}
}kdTree[maxn<<2], input[maxn];

struct People
{
	LL a,b,c;
}peo[maxn];

void updata(int cur)
{
	kdTree[cur].mi[0] = kdTree[cur].mx[0] = kdTree[cur].x[0];
	kdTree[cur].mi[1] = kdTree[cur].mx[1] = kdTree[cur].x[1];
	kdTree[cur].sum = kdTree[cur].h;
	if (kdTree[cur<<1].flag)
	{
		kdTree[cur].sum += kdTree[cur<<1].sum;
		kdTree[cur].mi[0] = min(kdTree[cur<<1].mi[0], kdTree[cur].mi[0]);
		kdTree[cur].mi[1] = min(kdTree[cur<<1].mi[1], kdTree[cur].mi[1]);
		kdTree[cur].mx[0] = max(kdTree[cur<<1].mx[0], kdTree[cur].mx[0]);
		kdTree[cur].mx[1] = max(kdTree[cur<<1].mx[1], kdTree[cur].mx[1]);
	}
	if (kdTree[cur<<1|1].flag)
	{
		kdTree[cur].sum += kdTree[cur<<1|1].sum;
		kdTree[cur].mi[0] = min(kdTree[cur<<1|1].mi[0], kdTree[cur].mi[0]);
		kdTree[cur].mi[1] = min(kdTree[cur<<1|1].mi[1], kdTree[cur].mi[1]);
		kdTree[cur].mx[0] = max(kdTree[cur<<1|1].mx[0], kdTree[cur].mx[0]);
		kdTree[cur].mx[1] = max(kdTree[cur<<1|1].mx[1], kdTree[cur].mx[1]);
	}
}

void build(int begin, int end, int cur, int dep)
{
	if (begin>end) return;
	depth = dep%k;
	int mid = begin+end>>1;
	nth_element(input+begin, input+mid, input+end+1);
	kdTree[cur] = input[mid];
	kdTree[cur].flag = true;
	build(begin, mid-1, cur<<1, dep+1);
	build(mid+1, end, cur<<1|1, dep+1);
	updata(cur);
}

bool ck(People &p, KdTreeNode &curNode) // 判断当前节点是否满足p的要求(甜度要求<p.c)
{
	return curNode.x[0]*p.a+curNode.x[1]*p.b<p.c;
}

void geth(People &p, KdTreeNode &node, LL &mi, LL &mx) // node为根节点的子树的启发式函数值, mi是最小值, mx是最大值
{
	mi = min(p.a*node.mi[0], p.a*node.mx[0]) + min(p.b*node.mi[1], p.b*node.mx[1]);
	mx = max(p.a*node.mi[0], p.a*node.mx[0]) + max(p.b*node.mi[1], p.b*node.mx[1]);
}

LL query(People &p, int cur)
{
	LL ans =0;
	KdTreeNode curNode = kdTree[cur];
	if (!curNode.flag) return 0LL;
	if (ck(p, curNode)) // 检查当前节点是否合乎要求
	{
		ans+=curNode.h;
	}
	LL mi, mx;
	geth(p,kdTree[cur<<1], mi, mx); // 计算左子树的启发式函数值(最小mi,最大mx)
	if (mi<p.c) // 如果mi>=p.c 则整棵子树都不需要考虑了
	{
		if (mx<p.c) // 如果左子树最大的都<p.c,则整棵树全部笑纳
		{
			ans+=kdTree[cur<<1].sum;
		}
		else // mi<p.c<=mx
		{
			ans+=query(p, cur<<1);
		}
	}
	geth(p, kdTree[cur<<1|1], mi,mx); // 计算右子树的启发式函数值(最小mi, 最大mx)
	if (mi<p.c)
	{
		if (mx<p.c)
		{
			ans+=kdTree[cur<<1|1].sum;
		}
		else
		{
			ans+=query(p, cur<<1|1);
		}
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&m);
	for (int i = 1; i<=n; i++)
	{
		scanf("%lld%lld%lld", &input[i].x[0], &input[i].x[1], &input[i].h);
	}
	for (int i = 1;i<=m; i++)
	{
		scanf("%lld%lld%lld", &peo[i].a, &peo[i].b, &peo[i].c);
	}
	build(1,n,1,0);
	for (int i = 1; i<=m; i++) // 遍历每个人
	{
		printf("%lld\n", query(peo[i], 1));
	}
	return 0;
}

ac情况（1A真开心~）

1
2
3
4
5
6
所属题目
P4475 巧克力王国
评测状态
Accepted
评测分数
100

参考

【1】https://yfsyfs.github.io/2019/09/20/%E6%B4%9B%E8%B0%B7-P4357-CQOI2016-K%E8%BF%9C%E7%82%B9%E5%AF%B9-kd%E6%A0%91/