[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$ 條線段交了。
題目大意:
給定一個圓,在圓周上有 $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;
}
留言
張貼留言