[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;
} 

留言

  1. Independent consultants play, review and rank the most effective live dealer on-line casinos for Korea. So how do you go about discovering an internet casino that accepts South Korean gamers AND ticks all of the above boxes? Trying to do the legwork on all that research yourself would take means too lengthy, so save yourself that unnecessary effort by benefiting from our 온라인카지노 onerous work! This website has been designed to give you all the data you need to|you should|you have to} determine which areas are worth your time and which are not. To ensure that that|be certain that} an internet casino in Korea is protected and legal, we only included the sites that have an official and legitimate license from a good regulatory physique. Moreover, each casino on our record is regularly audited for fairness by an impartial company, which means the games aren't rigged and the overall fairness is the very best possible.

    回覆刪除

張貼留言

這個網誌中的熱門文章

[IOICamp] 最小公倍數問題

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1209. 圖論 之 二分圖測試