ZOJ_3157 Weapon

题意:

给你平面上若干直线,问你在$(L,R)$这个区间内,有多少直线会相交

题解:

想象一下怎样的直线能够相交,设直线$Line_1$,直线$Line_2$与$x=L$的交点分别是$L_1,L_2$,与$x=R$的交点分别是$R_1,R_2$,设$L_1>L_2$,那么如果这两根直线在这个区间相交,则必有$R_1<R_2$。
所以这个问题就转换成了求逆序对的个数,维护一个树状数组即可。

代码:

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/ZOJ/3157.cpp