poj 3067 japan

 1 #include<iostream>
 2 #include<string>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<queue>
 6 #include<stack>
 7 #include<algorithm>
 8 #include<cstring>
 9 #include<stdlib.h>
10 #include<string>
11 #include<cmath>
12 using namespace std;
13 #define pb push_back
14 int n,m,k;
15 __int64 p[1100];
16 struct node{
17     int x,y;
18 }num[1001000];
19 int cmp(node a,node b){
20     if(a.x==b.x) return a.y<b.y;
21     return a.x<b.x;
22 }
23 void update(int pos){
24     while(pos>=1){
25         p[pos]+=1;
26         pos-=pos&(-pos);
27     }
28 }
29 __int64 getnum(int pos){
30     __int64 sum=0;
31     while(pos<=m){
32         sum+=p[pos];
33         pos+=pos&(-pos);
34     }
35     return sum;
36 }
37 int main(){
38     int t,cas=0;cin>>t;
39     while(t--){
40         cin>>n>>m>>k;
41         memset(p,0,sizeof(p));
42         for(int i=1;i<=k;i++)
43             scanf("%d%d",&num[i].x,&num[i].y);
44         sort(num+1,num+1+k,cmp);
45         __int64 ans=0;
46         for(int i=1;i<=k;i++){
47             ans+=getnum(num[i].y+1);
48             update(num[i].y);
49         }
50         printf("Test case %d: %I64d\n",++cas,ans);
51     }
52 }