/**//* 题意:给出一条直线上的点,每个点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
搜索
最新评论
|
|