求交点的个数;
容易发现,对于两条航线(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 begin10 inc(c[p]);11 p:=p+lowbit(p);12 end;13 end;14 function ask(p:longint):longint;15 begin16 ask:=0;17 while p<>0 do18 begin19 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 begin26 i:=l;27 j:=r;28 h:=x[(l+r) div 2];29 p:=y[(l+r) div 2];30 repeat31 while (x[i]j) then34 begin35 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