题目大意

给定 nn 个元素，每个元素有 si,fi,tis_i,f_i,t_i 三个属性，再给定 mm 个元素，每个元素有 lj,rj,bjl_j,r_j,b_j 三个属性，对于每一个 jj 求出满足 si≤ljs_i\le l_j 且 fi≥rjf_i\ge r_j 且 ti≥bjt_i\ge b_j 且 tit_i 最小的 ii。

Solution 1

根据题面，我们把前 nn 个元素称为公交车，后 mm 个元素称为人，同时为了方便，我们把 tit_i 和 bjb_j 统称为时间，sis_i 和 ljl_j 称为左端点，fif_i 和 rjr_j 称为右端点。

思路

看到这道题首先想到的是三维偏序，继而可以想到直接 CDQ 分治搞过去，如果您不会 CDQ 分治，建议先把 Solution 2 看了，再去学习一下。

其实个人感觉这道题就是 CDQ 的板子题，这里提醒两点就够了，由于求的是最小的 tit_i 的编号，所以用树状数组存的应该是 tit_i 的最小值以及这个最小的 tit_i 的编号，还有就是在一开始根据时间排序的时候，如果有两个时间相同的，那么公交车应该排在人的前面，具体的可以看代码。

参考代码

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
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N = 1e5 + 10, inf = 0x3f3f3f3f;
struct ALTXDY
{
	int tp, t, x, y, id;//tp 表示这是公交车还是人，t 是时间，x 是左端点，y 是右端点，id 是编号
	bool operator < (const ALTXDY &a) const
	{
		return t == a.t ? tp < a.tp : t > a.t;
	}
};
ALTXDY q[N<<1], tmp[N<<1];
int n, m, k, c[N<<2];//c 数组和 k 拿来对右端点离散化
pii tree[N<<1], ans[N];
void reset(int x)//cdq 时用来重置树状数组的
{
	for(; x <= k; x += lowbit(x))
		tree[x] = mp(inf, inf);
}
void update(int x, pii val)
{
	for(; x <= k; x += lowbit(x))
		tree[x] = min(tree[x], val);
}
pii query(int x)
{
	pii ans = mp(inf, inf);
	for(; x >= 1; x -= lowbit(x))
		ans = min(ans, tree[x]);
	return ans;
}
void cdq(int l, int r)
{
	if(l == r)
		return;
	int mid = (l+r)>>1;
	cdq(l, mid);
	cdq(mid+1, r);
	int i = l, j = mid+1, cnt = l-1;
	while(i <= mid && j <= r)
	{
		if(q[i].x <= q[j].x)
		{
			tmp[++cnt] = q[i];
			if(q[i].tp == 0)
				update(k-q[i].y+1, mp(q[i].t, q[i].id));
            	//由于公交车的右端点要大于人的右端点，但我不会树状数组求区间最值，所以把右端点取个反再加上 k 就变成了小于，也就是一般的树状数组写法
			i++;
		}
		else
		{
			tmp[++cnt] = q[j];
			if(q[j].tp == 1)
				ans[q[j].id] = min(ans[q[j].id], query(k-q[j].y+1));
			j++;
		}
	}
	while(i <= mid)
	{
		tmp[++cnt] = q[i];
		i++;
	}
	while(j <= r)
	{
		tmp[++cnt] = q[j];
		if(q[j].tp == 1)
			ans[q[j].id] = min(ans[q[j].id], query(k-q[j].y+1));
		j++;
	}
	for(int i = l; i <= r; i++)
		reset(k-q[i].y+1);
	for(int i = l; i <= r; i++)
		q[i] = tmp[i];
}
int main()
{
	memset(ans, inf, sizeof(ans));
	memset(tree, inf, sizeof(tree));
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		int t, s, f;
		scanf("%d%d%d", &s, &f, &t);
		q[i]=(ALTXDY){0, t, s, f, i};//公交车 tp 为 0
		c[++k] = f;
	}
	for(int i = 1; i <= m; i++)
	{
		int b, l, r;
		scanf("%d%d%d", &l, &r, &b);
		q[i+n] = (ALTXDY){1, b, l, r, i};//人 tp 为 1
		c[++k] = r;
	}
	sort(c+1, c+1+k);
	k = unique(c+1, c+1+k)-c-1;
	for(int i = 1; i <= n+m; i++)
		q[i].y = lower_bound(c+1, c+1+k, q[i].y)-c;
	sort(q+1, q+1+n+m);
	cdq(1, n+m);
	for(int i = 1; i <= m; i++)
		if(ans[i].first == inf)
			printf("-1 ");
		else
			printf("%d ", ans[i].second);
	return 0;
}

时间复杂度 O((n+m)log⁡2(n+m))O((n+m)\log^2(n+m))，跑个 1×1051\times 10^5 问题不大。

Solution 2

因为看见我这个代码是洛谷上的最劣解，去看了一下题解区，才发现原来有一个 O((n+m)log⁡(n+m))O((n+m)\log(n+m)) 的做法。

思路

这道题用 CDQ 分治其实有点可惜，因为对于每一个人，我们要找的只是满足条件的最小的那个 tit_i，至于其他的，我们根本不用考虑，这就有了第二种做法。

首先，我们根据左端点排个序，相同的还是公交车排在人的前面，然后我们从前往后扫一遍，如果遇到公交车，我们就以它的时间为下标，右端点和其编号为值塞到一棵线段树里，并维护右端点的最大值。

接下来是重点，如果遇到人，显然此时塞到线段树里的公交车的左端点都小于等于这个人，那么我们就在线段树上找一个叶子节点，满足这个叶子节点所代表的 tit_i（也就是它这个位置所代表的下标）比这个人的时间大，并且它所存的右端点也比这个人的右端点大，而且这个叶子节点尽量靠左。

具体来说，我们在 bjb_j（也就是这个人的时间）到 kk（此时 kk 用来离散化时间）这个区间里操作，对于当前节点 ii，如果它的左儿子是合法的（即这个儿子是存在的，并且所代表的区间与 [bj,k][b_j,k] 有交集，并且这个儿子所代表的区间中的右端点的最大值比这个人的右端点大），那么我们就继续对这个儿子进行递归，如果它不合法，我们再判断右儿子是否合法，如果两个都不合法，那么就直接返回 −1-1，如果递归到了叶子节点，就说明这个叶子节点所代表的就是满足所有条件且 tit_i 最小的那一个公交车，直接返回它所存的编号即可。

为什么这样是对的呢？首先，对于节点 ii，如果其左儿子是合法的，那我们一定不会去考虑它的右儿子，如果左儿子不合法，我们才会考虑右儿子，其次，如果某个节点所代表的区间中的最大值还没有要求值大，那它肯定是不合法的（其实个人感觉这很显然吧）。

参考代码

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
#include <bits/stdc++.h>
using namespace std;
namespace IO
{
	char buf[1<<22], *p1 = buf, *p2 = buf;
	#define getchar() (p1 == p2 && (p2 = (p1 = buf)+fread(buf, 1, 1<<21, stdin), p1==p2) ? EOF : *p1++)
	#define isdigit(c) (c >= 48 && c <= 57)
	#define isalpha(c) ((c >= 65 && c <= 90) || (c >= 97 && c <= 122))
	template<typename T> inline void read(T &x)
	{
		x = 0;
		register char ch = getchar();
		while(!isdigit(ch))
			ch = getchar();
		while(isdigit(ch))
		{
			x = (x<<1)+(x<<3)+(ch^48);
			ch = getchar();
		}
	}
	template <typename T,typename... Args> inline void read(T& t, Args&... args)
	{
		read(t);read(args...);
	}
}
using namespace IO;
const int N = 1e5 + 10, inf = 0x3f3f3f3f;
struct ALTXDY
{
	int tp, t, x, y, id;
	bool operator < (ALTXDY const &a) const
	{
		return x == a.x ? tp < a.tp : x < a.x;
	}
};
ALTXDY q[N<<1];
int n, m, tot, bus[N], ans[N], c[N<<1], dat[N<<2], ls[N<<2], rs[N<<2];
void update(int &i, int l, int r, int x, int k)
{
	if(!i)
		i=++tot;
	if(bus[dat[i]] < bus[k])
		dat[i] = k;
	if(l == r)
		return;
	int mid = (l+r)>>1;
	if(x <= mid)
		update(ls[i], l, mid, x, k);
	else
		update(rs[i], mid+1, r, x, k);
}
int query(int i, int l, int r, int x, int y, int val)
{
	if(l == r)
		return dat[i];
	int mid = (l+r)>>1, t = -1;
	if(x <= mid && ls[i] && bus[dat[ls[i]]] >= val)
		t = query(ls[i], l, mid, x, y, val);
	if(t == -1 && y >= mid+1 && rs[i] && bus[dat[rs[i]]] >= val)
		t = query(rs[i], mid+1, r, x, y, val);
	return t;
}
int main()
{
	read(n, m);
	for(int i = 1; i <= n; i++)
	{
		int s, f, t;
		read(s, f, t);
		q[i] = (ALTXDY){0, t, s, f, i};
		c[i] = t;
		bus[i] = f;
	}
	for(int i = 1; i <= m; i++)
	{
		int b, l, r;
		read(l, r, b);
		q[i+n] = (ALTXDY){1, b, l, r, i};
		c[i+n] = b;
	}
	sort(c+1, c+1+n+m);
	register int k = unique(c+1, c+1+n+m)-c-1;
	for(int i = 1; i <= n+m; i++)
		q[i].t = lower_bound(c+1, c+1+k, q[i].t)-c;
	sort(q+1, q+1+n+m);
	register int rt = 0;
	for(int i = 1; i <= n+m; i++)
		if(q[i].tp == 0)
			update(rt, 1, k, q[i].t, q[i].id);
		else
			ans[q[i].id] = query(rt, 1, k, q[i].t, k, q[i].y);
	for(int i =1; i <= m; i++)
		printf("%d ", ans[i]);
	return 0;
}

因为常数不太优秀，加了一发 fread，又把原来的 pair 换了一下，最后 CF 上 rk4，洛谷上 rk1。

Update

今天机房里一个大佬对这个算法的时间复杂度提出了质疑，他认为根据一个节点的最大值来判断这个区间里有没有合法的解是不对的，原因如下。

考虑有这样一个节点 uu（就是图中最上面的那个长方形），它包含了一部分要查询的这个区间（也就是图中的下面那条线段），而被这个节点包含的这部分区间中的值最大只有 66，但在这个节点代表的区间中还存在一个数，它不被包含在要查询的区间里，但它的值是 77，假设此时我们需要使找到的叶子结点的值大于等于 77，那么对于 uu，我们就会查询失败，需要回溯以后重新查找，而那位大佬认为这个过程是可以卡掉的。

但是，实际上查找的过程还是 O(log⁡n)O(\log n) 的！

为什么呢？我们考虑在什么情况下这个节点会查找失败，显然只有上面这一种情况，也就是一个节点只包含了一部分要查询的区间。

然后思考如果查询失败，我们会回到哪一个节点开始重新查找。

显然，对于这样一类节点 uu，它的右儿子一定是被完全包含于要查询的区间内的，此时我们就可以通过它所存的最大值来判断它是否合法，而在这个右儿子的子树中一定不会存在和 uu 相同的情况，所以，如果右儿子合法，那我们就一定能找到一个合法的解，而如果右儿子不合法，那我们也无须再递归了，所以，我们最多只会出现一次查询失败的情况，最终时间复杂度还是 O(log⁡n)O(\log n) 的。

顺便说一句，由于我们查找的这个区间的右端点总是和整棵线段树所代表的区间的右端点相同，所以在右端点并不会出现上述情况。

反思

CDQ 分治还是有点不太熟练，从写到 AC 花了三节课的时间，以后还是应该多练习一下。