 /**//*
題意:給出一條直線上的點,每個點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
搜索
最新評論

|
|