CF1311F的题解

osfly / 2023-08-25 / 原文

前置芝士：二维偏序。

二维偏序的板子题。

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

考虑点对 \((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;
}