CF1311F Moving Points
题目描述
在数轴 $OX$ 上有 $n$ 个点。第 $i$ 个点最初在坐标 $x_i$, 并且有一个速度 $v_i$。没有两个点的坐标是相同的。所有的点都按照不变的速度移动,第 $i$ 个点在 $t$ 时刻的坐标为 $x_i + t \cdot v_i$ ($t$ 可能不是整数)。
对于两个点 $i$ 和 $j$,设 $d(i,j)$ 为 $i$ 和 $j$ 在任意时刻下的可能的最小距离(时刻可能不是整数)。如果 $i$ 和 $j$ 在某一时刻重合,那么 $d(i,j)=0$。
你的任务是计算出下面这个式子的值(对于任意两个点的最小距离之和):
$$
\sum_{1\leq i < j \leq n}d(i,j)
$$
输入格式
第一行是一个整数 $n\ (2\leq n \leq 2\times 10^5)$, 表示点的个数。
第二行包含 $n$ 个整数 $x_1,x_2,\dots,x_n\ (1\leq x_i \leq 10^8)$,$x_i$ 表示第 $i$ 个点的初始坐标。数据保证没有重复的 $x_i$。
第三行包含 $n$ 个整数 $v_1,v_2,\dots,v_n\ (-10^8 \leq v_i \leq 10^8)$,$v_i$ 表示第 $i$ 个点的初始速度。
输出格式
输出一个整数,表示任意两个点的最小距离之和,即
$$
\sum_{1\leq i < j \leq n}d(i,j)
$$