codeforces 1311 F. Moving Points （樹狀數組 + 離散化）

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

3
1 3 2
-100 2 3
           

output

Copy

3
           

input

Copy

5
2 1 4 3 5
2 2 2 3 4
           

output

Copy

19
           

input

Copy

2
2 1
-3 0
           

output

Copy

題意：

x軸上有n個點，點xi的移動速度為vi（沿x軸移動），問每兩點之間可以達到的最近距離之和。（不一定是同一時刻） 

思路：

對于任意兩點 x1 < x2 && v1 <= v2 時這兩點無法相遇，對結果貢獻 x2 - x1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;

int n, m;
ll sum[N], cnt[N], v[N];    //sum[]坐标字首和，cnt[i]左邊比現在坐标小、速度小的點的數量，v[]速度離散化數組

struct node
{
    int x, v;
} s[N];

bool cmp(node a, node b)
{
    return a.x < b.x;
}

void init()
{
    memset(sum, 0, sizeof(sum));
    memset(cnt, 0, sizeof(cnt));
}

int lowbit(int x)
{
    return (-x) & x;
}

void add(int pos, int x, ll c[])
{
    while(pos <= n)
    {
        c[pos] += x;
        pos += lowbit(pos);
    }
}

ll query(int pos, ll c[])
{
    ll res=0;
    while(pos>0)
    {
        res += c[pos];
        pos -= lowbit(pos);
    }
    return res;
}

int main()
{
    while(~scanf("%d", &n))
    {
        init();
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &s[i].x);
        }
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &s[i].v);
            v[i] = (ll)s[i].v;
        }
        sort(s + 1, s + n + 1, cmp);                    //對坐标從小到大排序
        sort(v + 1, v + n + 1);
        int tot = unique(v + 1, v + n + 1) - v - 1;     //去重
        ll ans = 0;
        for(int i = 1; i <= n; ++i)                     //按坐标從小到大枚舉
        {
            int id = lower_bound(v + 1, v + tot + 1, s[i].v) - v;    //比該點速度小的速度有多少個（這個點的速度是第幾小）
            ans += (ll)query(id, cnt) * s[i].x - query(id, sum);     //樹狀數組求區間和：符合條件的點數 * 該點坐标 - 符合條件的點的坐标和
            add(id, s[i].x, sum);    //坐标和
            add(id, 1, cnt);         //點數++
        }
        cout<<ans<<'\n';
    }
    return 0;
}