题目大意

给定 nn 个元素,每个元素有 si,fi,tis_i,f_i,t_i 三个属性,再给定 mm 个元素,每个元素有 lj,rj,bjl_j,r_j,b_j 三个属性,对于每一个 jj 求出满足 siljs_i\le l_jfirjf_i\ge r_jtibjt_i\ge b_jtit_i 最小的 ii

Solution 1

根据题面,我们把前 nn 个元素称为公交车,后 mm 个元素称为人,同时为了方便,我们把 tit_ibjb_j 统称为时间,sis_iljl_j 称为左端点,fif_irjr_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)log2(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。

反思

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