tjut 3015

#include<iostream> #include<algorithm> using namespace std; #define M 100005 struct node { __int64 a,b; int num1,num2; }t[M]; int cmpa(node &p,node &q) { if(p.a<q.a) return 1; else return 0; } int cmpb(node &p,node &q) { if(p.b<q.b) return 1; else return 0; } int cmpn(node &p,node &q) { if(p.num2<q.num2) return 1; else return 0; } __int64 c[M],d[M],n; //c用来处理一个数前面或者后面比它大或者小的数之和，d用来处理这个数前面或者后面有多少个数 int lowbit(int x) //比它大或者小 { return x&(-x); } void updatac(int i,int j) { while(i<=n) { c[i]+=j; i+=lowbit(i); } } void updatad(int i,int j) { while(i<=n) { d[i]+=j; i+=lowbit(i); } } __int64 getsumc(int x) { __int64 s=0; while(x>0) { s+=c[x]; x-=lowbit(x); } return s; } __int64 getsumd(int x) { __int64 s=0; while(x>0) { s+=d[x]; x-=lowbit(x); } return s; } int main() { while(scanf("%d",&n)>0) { memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); int i; for(i=1;i<=n;i++) { scanf("%I64d%I64d",&t[i].a,&t[i].b); } sort(t+1,t+1+n,cmpa); for(i=1;i<=n;i++) { if(i!=1&&t[i].a==t[i-1].a) t[i].num1=t[i-1].num1; else t[i].num1=i; } int max=t[n].num1; //printf("%d\n",max); sort(t+1,t+1+n,cmpb); for(i=1;i<=n;i++) { if(i!=1&&t[i].b==t[i-1].b) t[i].num2=t[i-1].num2; else t[i].num2=i; } sort(t+1,t+1+n,cmpn); //这之前都是对等级进行处理 for(i=1;i<=n;i++) //插入数据 { updatac(t[i].num1,t[i].num1); updatad(t[i].num1,1); //printf("%d %d\n",t[i].num1,t[i].num2); } //printf("\n\n\n"); __int64 sum=0,m=n,tmp1,tmp2; for(i=1;i<n;i++) { //printf("%I64d\t %I64d\t %I64d\t %I64d\n",getsumc(max),getsumc(t[i].num1),n-getsumd(t[i].num1),t[i].num2); //sum+=(getsumc(max)-getsumc(t[i].num1)-(m-getsumd(t[i].num1))*t[i].num1)*t[i].num2; /* 在这里，sum错了一次，一开始是想，算出所有数之和-小于等于t[i].num1的数之和，再减去t[i].num1这个数与其他数相减的次数*t[i].num1； 这样做是错的，这组数据过不了： 4 1 1 2 4 3 1 4 3 4 正确结果是37. */ //printf("%I64d\t%I64d\n",getsumc(max),getsumc(100)); tmp1=getsumd(t[i].num1-1)*t[i].num1-getsumc(t[i].num1-1); tmp2=(getsumd(max)-getsumd(t[i].num1))*t[i].num1-(getsumc(max)-getsumc(t[i].num1)); /* 之后，我再思考，发现可以先求出t[i].num后面比t[i].num小、大的数之和，还有比它小、大的数的个数，用比它小的数的个数*它本身-比 它小的数之和，再求出比它大的数的个数*它本身-比它大的数.............；再这两个数相减....结果就出来了；但是，每求出一个数后， 要把这个数删除，以免下面会重复求这个数............. */ sum+=(tmp1-tmp2)*t[i].num2; updatac(t[i].num1,-t[i].num1); updatad(t[i].num1,-1); m--; } printf("%I64d\n",sum); } return 0; }