yukicoder 743 - Segments on a Polygon

問題

m頂点の凸多角形があり、各頂点には0〜m-1の番号が割り振られている
ここに2つの頂点同士を結ぶような線分をn個追加する
追加した線分同士の交点の数を求めよ

1 <= n <= 10^5
3 <= m <= 2*10^5

解法

任意のiでa[i] < b[i]となるようにswapし、線分たちをa[i]の昇順にソートすると、i本目の線分がj(＜i)本目の線分と交わるのは
a[i] < b[j] < b[i]
を満たすときになる
BITで↑を満たすようなjの個数を求めていけばいい

ll n, m, x, y, res;
pair<int,int> p[100100];
BIT<int,20> b;

signed main() {
	cin >> n >> m;
	rep(i,n) {
		cin >> x >> y;
		if (x>y) swap(x,y);
		p[i] = {x,y};
	}
	sort(p,p+n);
	rep(i,n) {
		res += b.sum(p[i].second) - b.sum(p[i].first);
		b.add(p[i].second, 1);
	}
	cout << res << endl;
}