卿学姐与城堡的墙
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
卿学姐终于来到了魔王的城堡，城堡修建的十分壮观。
即使心中放不下公主，卿学姐还是忍不住驻足观赏这宏伟的建筑。
卿学姐注意到城堡的墙上有若干直线状的花纹。
可以将墙看做一个平面，卿学姐想知道有多少种方式任取两个直线，使得这两个直线的交点的横坐标xx满足：u≤x≤vu≤x≤v。
Input
第一行三个整数N,u,vN,u,v，标明直线有NN条。
接下来有NN行，每行两个整数k,bk,b，表示这条直线是y=kx+by=kx+b
1≤N≤2000001≤N≤200000
0≤|k|≤10000000000≤|k|≤1000000000
0≤|b|≤10000000000≤|b|≤1000000000
0≤|u|≤10000000000≤|u|≤1000000000
0≤|v|≤10000000000≤|v|≤1000000000
输入保证u≤vu≤v，保证没有两条直线是一样的
Output
输出一个整数，代表选择的方法数。
Sample input and output
| Sample Input | Sample Output |
|---|---|
3 -3 1-1 32 21 1 | 3 |
Hint
上图是样例的解释，交点是A,B,C
其实就是求逆序对数，先分别算出与u的交点和与v的交点，把u从小到大排序，然后依次把与v的交点加入树状数组，因为后加入的直线与u的交点肯定大于先加入直线与u的交点，所以后加入的直线与v的交点只要小于或者等于先加入的直线与v的交点就可以判断出必定相交，也就成了求逆序对数的问题了，还要离散化，因为数据范围都太大了。。。
#pragma GCC diagnostic error "-std=c++11"#include#include #include #include #include using namespace std;typedef long long LL;const int N = 200000 + 5;struct Point{ LL x, y; bool operator < (const Point &X) const{ if(x != X.x) return x < X.x; return y > X.y; }};int c[N << 1];vector a;vector tot;LL Query(int x){ LL ret = 0; while(x){ ret += c[x]; x -= x&(-x); } return ret;}void change(int x){ while(x <= (int)tot.size()){ c[x]++; x += x&(-x); }}int main(){ //std::ios::sync_with_stdio(false); LL n, u, v, b, k; cin >> n >> u >> v; for(int i = 0; i < n; i++){ cin >> k >> b ; a.push_back((Point){k*u+b, k*v+b}); tot.push_back(a[i].x); tot.push_back(a[i].y); } sort(tot.begin(), tot.end()); tot.resize(distance(tot.begin(), unique(tot.begin(), tot.end()))); for(Point &i:a){ i.y = (LL)(lower_bound(tot.begin(), tot.end(), i.y) - tot.begin()) + 1; i.x = (LL)(lower_bound(tot.begin(), tot.end(), i.x) - tot.begin()) + 1; } sort(a.begin(), a.end()); LL ans = 0; for(Point &i:a){ ans += Query((int)tot.size()) - Query(i.y - 1); change(i.y); } cout << ans << endl;}