 /**//*
题意:给出一条直线上的点,每个点xi有值vi 每一对(i,j)的值为:dis(ti,j)*max(vi,vj)
现求所有C(N,2)对点的所有值 O(n^2)会Tle
先按照V排序!
用两个一维树状数组,分别记录小于xi的点的个数pre_cnt以及小于xi点的距离之和pre_dist
对于i之前的点xj,分xj<xi和xj>xi计算:
ans+=(long long)v*(pre_cnt*x-pre_dist + total_dist-pre_dist-(i-pre_cnt)*x);
total_dist为i-1个点的x坐标之和
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 20000;

struct Cow
  {
int v,x;
bool operator<(const Cow &c)const
 {
return v<c.v;
}
}cows[MAXN+5];

int cnt_C[MAXN+5],dist_C[MAXN+5];
int N;

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

void insert(int *a,int p,int x)
  {
while(p<=MAXN)
 {
a[p]+=x;
p+=lowbit(p);
}
}

int sum(int *a,int p)
  {
int ans = 0;
while(p>0)
 {
ans+=a[p];
p-=lowbit(p);
}
return ans;
}

int main()
  {
while(~scanf("%d",&N))
 {
for(int i=0;i<N;i++)
scanf("%d%d",&cows[i].v,&cows[i].x);
sort(cows,cows+N);
long long ans = 0;
int total_dist = 0;
for(int i=0;i<N;i++)
 {
int x = cows[i].x,v=cows[i].v;
int pre_dist = sum(dist_C,x),pre_cnt = sum(cnt_C,x);//no two in the same pos
ans+=(long long)v*(pre_cnt*x-pre_dist + total_dist-pre_dist-(i-pre_cnt)*x);//i从0开始
insert(dist_C,x,x);
insert(cnt_C,x,1);
total_dist+=x;
}
printf("%lld\n",ans);
}
return 0;
}
hdu 3015 跟这个类似,不过要先离散化
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|