【线段树】99pts求助
查看原帖
【线段树】99pts求助
481330
sunyizhe还是MC大佬楼主2023/1/15 17:38
//程序算法:线段树,排序 
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
struct Cow{
	int v,x;
	bool operator < (const Cow& rhs) const {
		return v<rhs.v;
	}
}c[N];
struct Node{
	int l,r;
	long long sum,cnt;//坐标和,牛的个数。 
}t[N*4];
void build(int rt,int l,int r)
{
	t[rt].l=l,t[rt].r=r;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
}
void modify(int rt,int x)
{
	if(t[rt].l==t[rt].r)
	{
		t[rt].cnt++;
		t[rt].sum+=x;
		return; 
	}
	int mid=(t[rt].l+t[rt].r)>>1;
	if(x<=mid)modify(rt*2,x);
	else modify(rt*2+1,x);
	t[rt].cnt=t[rt*2].cnt+t[rt*2+1].cnt;
	t[rt].sum=t[rt*2].sum+t[rt*2+1].sum;
}
pair<long long,long long> query(int rt,int l,int r)
{
	if(t[rt].l>=l&&t[rt].r<=r)
		return make_pair(t[rt].cnt,t[rt].sum);
	long long cnt=0,sum=0;
	int mid=(t[rt].l+t[rt].r)>>1;
	if(l<=mid)
	{
		pair<long long,long long> tmp=query(rt*2,l,r);
		cnt+=tmp.first;
		sum+=tmp.second;
	}
	if(r>mid)
	{
		pair<long long,long long> tmp=query(rt*2+1,l,r);
		cnt+=tmp.first;
		sum+=tmp.second;
	}
	return make_pair(cnt,sum);
}
int n;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&c[i].v,&c[i].x);
	sort(c+1,c+n+1);
	build(1,1,n);
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		pair<long long,long long> tmp;
		tmp=query(1,1,c[i].x-1);
		ans+=(tmp.first*c[i].x-tmp.second)*c[i].v;
		tmp=query(1,c[i].x,n);
		ans+=(tmp.second-tmp.first*c[i].x)*c[i].v;
		modify(1,c[i].x);
	}
	printf("%lld\n",ans);
	return 0;
}
2023/1/15 17:38
加载中...