[AtCoder] [經典競程 90 題] 017 - Crossing Segments（★7）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_q
題目大意:
給定一個圓，在圓周上有 $N$ 個點，每個點距離相同，接著我們畫 $M$ 條線段，分別從第 $L_i$ 個點連到第 $R_i$ 個點。問有多少組有交的線段 (這裡有交限定交在非端點上)。

---

想一下後可以發現兩個線段 $i$, $j$ 有交必定有一個 $j$ 的端點在 $L_i$ 與 $R_i$ 之間，另一個在外面。所以我們可以考慮對於每個線段，在 $L_j$ 的地方紀錄 $R_j$ ，並在 $R_j$ 的地方紀錄 $L_j$ ，這樣我們就可以透過查詢 $L_i$ 與 $R_i$ 之間有多少數字小於 $L_i$ 或大於 $R_i$ 就可以知道有多少線段跟第 $i$ 條線段交了。

#include <bits/stdc++.h>
using namespace std;
const int N = 300000 + 5;

class SegTree {
private:
	int n;
	vector<vector<int>> a;
	function<int(int, int)> policy;
	inline int lc(int x) { return 2 * x + 1; }
	inline int rc(int x) { return 2 * x + 2; }
	void build(int l, int r, int id, const vector<vector<int>> &v) {
		if (r - l == 1) {
			a[id] = v[l];
			sort(a[id].begin(), a[id].end());
			return;
		}
		int m = (l + r) >> 1;
		build(l, m, lc(id), v);
		build(m, r, rc(id), v);
		merge(a[lc(id)].begin(), a[lc(id)].end(), a[rc(id)].begin(), a[rc(id)].end(), back_inserter(a[id]));
	}
	int query(int ql, int qr, int l, int r, int id, int k) {
		if (qr <= l or r <= ql) return 0;
		if (ql <= l and r <= qr) {
			return policy(id, k);
		}
		int m = (l + r) >> 1;
		return query(ql, qr, l, m, lc(id), k) + query(ql, qr, m, r, rc(id), k);
	}
public:
	void build(int n_, const vector<vector<int>> &v) {
		n = n_; a.resize(n << 2);
		build(0, n, 0, v);
	}
	int query_gt(int l, int r, int k) {
		// [l, r) # > k
		policy = [this](int id, int x) {
			auto it = upper_bound(a[id].begin(), a[id].end(), x);
			return static_cast<int>(distance(it, a[id].end()));
		};
		return query(l, r, 0, n, 0, k);
	}
	int query_lt(int l, int r, int k) {
		// [l, r) # < k
		policy = [this](int id, int x) {
			auto it = lower_bound(a[id].begin(), a[id].end(), x);
			return static_cast<int>(distance(a[id].begin(), it));
		};
		return query(l, r, 0, n, 0, k);
	}
} seg;

int l[N], r[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		cin >> l[i] >> r[i];
		--l[i], --r[i];
	}
	vector<vector<int>> v(n);
	for (int i = 0; i < m; ++i) {
		v[l[i]].push_back(r[i]);
		v[r[i]].push_back(l[i]);
	}
	int64_t ans = 0;
	seg.build(n, v);
	for (int i = 0; i < m; ++i) {
		ans += seg.query_lt(l[i] + 1, r[i], l[i]);
		ans += seg.query_gt(l[i] + 1, r[i], r[i]);
	}
	cout << ans / 2 << '\n';
	return 0;
}