本文共 2414 字，大约阅读时间需要 8 分钟。

F. Moving Points

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are nn points on a coordinate axis OXOX. The ii-th point is located at the integer point xixi and has a speed vivi. It is guaranteed that no two points occupy the same coordinate. All nn points move with the constant speed, the coordinate of the ii-th point at the moment tt (tt can be non-integer) is calculated as xi+t⋅vixi+t⋅vi.

Consider two points ii and jj. Let d(i,j)d(i,j) be the minimum possible distance between these two points over any possible moments of time (even non-integer). It means that if two points ii and jj coincide at some moment, the value d(i,j)d(i,j) will be 00.

Your task is to calculate the value ∑1≤i<j≤n∑1≤i<j≤n d(i,j)d(i,j) (the sum of minimum distances over all pairs of points).

Input

The first line of the input contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the number of points.

The second line of the input contains nn integers x1,x2,…,xnx1,x2,…,xn (1≤xi≤1081≤xi≤108), where xixi is the initial coordinate of the ii-th point. It is guaranteed that all xixi are distinct.

The third line of the input contains nn integers v1,v2,…,vnv1,v2,…,vn (−108≤vi≤108−108≤vi≤108), where vivi is the speed of the ii-th point.

Output

Print one integer — the value ∑1≤i<j≤n∑1≤i<j≤n d(i,j)d(i,j) (the sum of minimum distances over all pairs of points).

Examples

input

Copy

31 3 2-100 2 3

output

Copy

3

input

Copy

52 1 4 3 52 2 2 3 4

output

Copy

19

input

Copy

22 1-3 0

output

Copy

0

【题意】

给你n个点，每个点有一个速度v，对于任意时刻，每个点的位置为x+vt。问对于所有点i，j，∑1≤i<j≤n d(i,j)的最小值是多少。

题解：简单推算可以发现，对于每个位置，考虑位置在它左面且速度比他小的或者在它右面速度比他大的，只有这两种情况答案不为0，其他早晚会相遇，为0，这两种情况是我们需要计算的值，这两种其实是同一种情况，以每个位置为右端点，这样只需找出第i个位置左面所有比他速度小的数。将速度离散化（和速度无关）后，将位置排序，对于每个位置，ans+=这个位置的x*（比他速度小的点的数量）-（比他速度小的点的x的和）。求和就要想到树状数组，用两个树状数组num，和sum分别维护这两个变量。

#include
   
    #define ll long longusing namespace std;const int maxx=2e5+100;struct node{	int x,v;	bool operator<(const node &a)const //先把x排序，直接排完	{		return x
    
     >n;	for(int i=1;i<=n;i++)         cin>>p[i].x;	for(int i=1;i<=n;i++) 	cin>>p[i].v,b[i]=p[i].v;	sort(p+1,p+1+n);	sort(b+1,b+1+n);	int len=unique(b+1,b+1+n)-b-1;//速度去重	init();	ll ans=0;	for(int i=1;i<=n;i++)	{		int pos=lower_bound(b+1,b+1+len,p[i].v)-b;//有多少个速度比它小的		ans+=query(num,pos)*(ll)p[i].x-query(sum,pos);		add(num,pos,1);//前面比他速度小的点的数量		add(sum,pos,p[i].x);//前面比他速度小的点的x之和	}	cout<
     
      <
     
    
   

 

转载地址：http://utyzi.baihongyu.com/