poj1990.rar_POJ 19_poj_poj19

//对v(i)排序，求出当前小于x的坐标和，和个数 #include<stdio.h> #include<memory.h> #include<algorithm> using namespace std; struct Point { int x,v; }; Point point[20001]; __int64 ans = 0; bool cmp(Point a,Point b)//对v排序 { if(a.v<b.v || (a.v == b.v && a.x < b.x))return true; return false; } int lowbit(int num) { return num&(num^(num-1)); } void Modify(int array[],int pos,int num,int n) { while(pos <= n) { array[pos]+=num; pos += lowbit(pos); } } int query(int array[],int end) { int sum = 0; while(end>=1) { sum += array[end]; end -= lowbit(end); } return sum; } int main() { int n,i,count,total,alltotal,bigtotal,xmax; int xtotal[20001]; int xcount[20001]; __int64 temp; xmax = 0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&point[i].v,&point[i].x); if(point[i].x>xmax) xmax = point[i].x; } sort(point,point+n,cmp); memset(xcount,0,sizeof(xcount)); memset(xtotal,0,sizeof(xtotal)); Modify(xcount,point[0].x,1,xmax); Modify(xtotal,point[0].x,point[0].x,xmax); alltotal = point[0].x; // printf("%d %d\n",point[0].x,point[1].x); for(i=1;i<n;i++) { count = query(xcount,point[i].x); total = query(xtotal,point[i].x); bigtotal = alltotal - total; temp = (2*count - i)*point[i].x -total + bigtotal; ans += point[i].v*temp; // printf("%d %d %I64d \n",count,total,ans); alltotal += point[i].x; Modify(xcount,point[i].x,1,xmax); Modify(xtotal,point[i].x,point[i].x,xmax); } printf("%I64d\n",ans); return 0; }