题意就是让你求交点有多少个。
我们可以先按a从小到大排序,a相等就按b从小到大排序。
代码如下:
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <math.h> #define M 1005 #define LL long long using namespace std; int n,m,k; int c[M]; struct node { int x,y; bool operator < ( const node &h ) const { return x<h.x || (x==h.x && y<h.y); } }; struct node p[M*M]; int Lowbit(int x) { return x&(-x); } void Update(int x,int d) { while(x<=M) { c[x]+=d; x+=Lowbit(x); } } int Sum(int x) { int sum=0; while(x>0) { sum+=c[x]; x-=Lowbit(x); } return sum; } int main() { int t; scanf("%d",&t); for(int count=1;count<=t;count++) { memset(c,0,sizeof(c)); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=k;i++) { scanf("%d%d",&p[i].x,&p[i].y); } sort(p+1,p+1+k); LL ans=0; for(int i=1;i<=k;i++) { Update(p[i].y,1); ans+=(i-Sum(p[i].y)); } printf("Test case %d: %lld\n",count,ans); } return 0; }