mxqz cdq四位偏序有没有更简单的做法
  • 板块学术版
  • 楼主fast_photon猫娘希儿
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/9/11 21:39
  • 上次更新2023/10/27 11:56:24
查看原帖
mxqz cdq四位偏序有没有更简单的做法
302805
fast_photon猫娘希儿楼主2022/9/11 21:39

RT,准备放到模拟赛签到题
题目大意:
给定 2n2n 个点的坐标,第 2k12k-1 和第 2k2k 个为一组,记为 AiA_iBiB_i,坐标形如 (Ai.x,Ai.y)(A_i.x,A_i.y)
每次询问给定两个点 CCDD,问有多少个 ii 满足 Ai.x>C.x,Ai.y>C.y,Bi.x<D.x,Bi.y<D.yA_i.x>C.x,A_i.y>C.y, B_i.x<D.x, B_i.y<D.y
并且题目满足 C.x<D.x,C.y<D.y,Ai.x<Bi.x,Ai.y<Bi.yC.x<D.x,C.y<D.y,A_i.x<B_i.x,A_i.y<B_i.y
换句话说,如果一个点的2个坐标分别小于另一个点的两个坐标,称之为在另一个点的左上方。现有 nn 组A,B,满足A在B的左上方,每次给定一组C和D,满足C在D的左上方,问有多少组A和B满足C在A的左上方,B在D的左上方
再换句话,给定 n组,每组两个点,满足上面的左上方条件,每次选中一个长方形区域,问区域内有多少组点(一组中两个点都在区域内称这一组在区域内)

2022/9/11 21:39
加载中...