求交点的个数；
容易发现，对于两条航线(xi,yi)和(xj,yj)，设xi<xj
只有yi>yj时两条航线存在交点；
于是我们考虑以x为第一关键字减序，y为第二关键字为减序排序；
则对于当前航线（xi,yi)，只要找之前所有yj小于yi的个数
所有交点数就是其总和，统计就要用到飘逸的树状数组了~
1 var a,c:array[0..1010] of longint; 2 x,y:array[0..1000010] of longint; 3 i,j,n,m,k,t:longint; 4 ans:int64; 5 6 procedure add(p:longint); 7 begin 8 while p<=m do 9 begin 10 inc(c[p]); 11 p:=p+lowbit(p); 12 end; 13 end; 14 function ask(p:longint):longint; 15 begin 16 ask:=0; 17 while p<>0 do 18 begin 19 ask:=ask+c[p]; 20 p:=p-lowbit(p); 21 end; 22 end; 23 procedure sort(l,r: longint); 24 var i,j,h,p: longint; 25 begin 26 i:=l; 27 j:=r; 28 h:=x[(l+r) div 2]; 29 p:=y[(l+r) div 2]; 30 repeat 31 while (x[i]<h) or (x[i]=h) and (y[i]<p) do inc(i); 32 while (h<x[j]) or (x[j]=h) and (p<y[j]) do dec(j); 33 if not(i>j) then 34 begin 35 swap(x[i],x[j]); 36 swap(y[i],y[j]); 37 inc(i); 38 j:=j-1; 39 end; 40 until i>j; 41 if l<j then sort(l,j); 42 if i<r then sort(i,r); 43 end; 44 45 begin 46 readln(t); 47 for i:=1 to t do 48 begin 49 readln(n,m,k); 50 for j:=1 to k do 51 readln(x[j],y[j]); 52 ans:=0; 53 sort(1,k); 54 fillchar(c,sizeof(c),0); 55 fillchar(a,sizeof(a),0); 56 inc(a[y[k]]); 57 add(y[k]); 58 for j:=k-1 downto 1 do 59 begin 60 ans:=ans+ask(y[j]-1); //这是唯一要注意的细节，交点一定不能在城市处 61 inc(a[y[j]]); 62 add(y[j]); 63 end; 64 writeln('Test case ',i,': ',ans); 65 end; 66 end.