题目解析 我们可以把所有的照片和相框的宽度和长度放在一块，并按照宽度从大到小排序，如果一个照片和一个相框的宽度相同，则将相框放在前面。 接下来准备一个容器 SSS，并遍历排序后的照片和相框： * 若当前为相框 (Ci,Di)(C_i, D_i)(Ci ,Di )，则将 DiD_iDi 放入 SSS 中。 * 若当前为照片 (Ai,Bi)(A_i, B_i)(Ai ,Bi )，则从 SSS 中找最小的大于等于 BiB_iBi 的元素，并将其从 SSS 中删除。如果无法找到这样的元素，说明这个照片无法找到一个相框来装裱，答案为 No\tt{No}No。 如果成功遍历完所有的元素，答案为 Yes\tt{Yes}Yes。 如果使用一个普通数组充当容器 SSS，那么以上算法的时间复杂度为 O(NM)O(NM)O(NM)，但是我们可以使用 std::multiset 作为 SSS 来解决这个问题，时间复杂度为： O((N+M)log⁡(N+M))O((N + M)\log{(N + M)})O((N+M)log(N+M))。 AC代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

题意解析：给定长度分别为 n,mn,mn,m 的两组点对 [(Ai,Bi)],[(Ci,Di)][(A_i,B_i)],[(C_i,D_i)][(Ai ,Bi )],[(Ci ,Di )]。你可以重排 [(Ai,Bi)][(A_i,B_i)][(Ai ,Bi )]。请你判断是否存在一种方式，使得对于所有 1≤i≤n1\le i\le n1≤i≤n，Ai≤CiA_i\le C_iAi ≤Ci 且 Bi≤DiB_i\le D_iBi ≤Di 。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 首先按 AiA_iAi 从大到小排序。这样对于 i≤ji\le ji≤j，Ai≥AjA_i\ge A_jAi ≥Aj 。然后分类讨论。 * 如果 Bi≥BjB_i\ge B_jBi ≥Bj ：显然 iii 怎么选都不影响后面的。 * 如果 Bi<BjB_i\lt B_jBi <Bj ：我们可以画图，发现 iii 选最下方的点是不劣的。 所以我们可以按如下方式选取： 找到 Di≥BiD_i\ge B_iDi ≥Bi 且 Ci≥AiC_i\ge A_iCi ≥Ai 且 DiD_iDi 最小的点。 现在的问题就转化成如何找到这个点。 我们可以先离散化一下 DiD_iDi ，然后开 mmm 个集合，将 DiD_iDi 相同的点都放到同一个集合里。 然后问题就是找到最小的 DiD_iDi ，使得 Di≥BiD_i\ge B_iDi ≥Bi 且它对应的集合内存在一个 Ci≥AiC_i\ge A_iCi ≥Ai ，找到删除这个集合的元素即可。 显然可以线段树二分。 时间复杂度：O(Tmlog⁡m)O(Tm\log m)O(Tmlogm)。