假设点 P 是 (x1,y1),点 Q 是 (x2,y2),那么满足覆盖的条件是:x1≥x2 and y1≥y2,最终的答案就是所有满足这样关系的点对个数。
由于 x 轴和 y 轴是独立的,我们这边只需要单独讨论,设所有纵坐标满足的方案数为 b 。
给定两个整数序列 A(长度 n)和 B(长度 m)。考虑从序列 A 中有序选取两个元素作为横坐标 x1,x2,从序列 B 中有序选取两个元素作为纵坐标 y1,y2。由此得到两个点 P(x1,y1) 和 Q(x2,y2)。
若点 Q 位于以原点 (0,0) 为左下角、点 P 为右上角的矩形内部或边界上,则称该矩形覆盖了点 Q,这等价于 x2≤x1 且 y2≤y1。
请你计算在所有可能的选取方案中,覆盖条件成立的方案总数。
注意:选取时允许重复选择同一元素,且选取的先后顺序不同视为不同方案。
数据范围:
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.