CF1311F 的题解

osfly · 2022-08-08 21:18:34 · 题解

前置芝士：二维偏序。

二维偏序的板子题。

怎么看出是二维偏序的呢？

考虑点对 (i,j)，令 x_i<x_j。

若 v_i>v_j，则两点会越来越近，易知最短距离为 0，所以我们不需要考虑这种情况。

所以问题转化成：x_i<x_j 且 v_i\le v_j 的点对的距离和。

很明显，二维偏序，套板子就行啦。

设已维护点的数量为 a，距离和为 b，则这个点的贡献为 x_i\times a-b。

#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
struct BIT
{
    int tree[200010];
    int lowbit(int x)
    {
        return x&(-x);
    }
    void update(int x,int num)
    {
        for(int i=x;i<=200000;i+=lowbit(i)) tree[i]+=num;
    }
    int query(int x)
    {
        int res=0;
        for(int i=x;i;i-=lowbit(i)) res+=tree[i];
        return res;
    }
}t[2];
int n;
struct point
{
    int x;
    int v;
}p[200010];
int lsh[200010];
int ans;
bool cmp(point a,point b)
{
    if(a.x==b.x) return a.v<b.v;
    return a.x<b.x;
}
void init()
{
    sort(lsh+1,lsh+1+n);
    int m=unique(lsh+1,lsh+1+n)-lsh-1;
    for(int i=1;i<=n;i++) p[i].v=lower_bound(lsh+1,lsh+1+m,p[i].v)-lsh;
    sort(p+1,p+1+n,cmp);
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&p[i].x);
    for(int i=1;i<=n;i++) scanf("%lld",&p[i].v),lsh[i]=p[i].v;
    init();
    for(int i=1;i<=n;i++)
    {
        int qwq=t[0].query(p[i].v),ry=t[1].query(p[i].v);
        ans+=ry*p[i].x-qwq;
        t[0].update(p[i].v,p[i].x),t[1].update(p[i].v,1);
    }
    printf("%lld",ans);
    return 0;
}