D - Intersecting Intervals

目錄

正向：

?反向：

---

正向：

從左往右掃描，記錄當前邊數。

來了新邊，它此刻與當前邊數相交，加到總數中。邊結束，當前邊數中減去即可。

const int maxn = 5e5+5;
int r[maxn], d[maxn];void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> r[i] >> d[i];}sort(r + 1, r + 1 + n);sort(d + 1, d + 1 + n);int ret = 0;int cur = 0;int i1 = 1, i2 = 1;while (i1 <= n && i2 <= n){if (r[i1] <= d[i2]){ret += cur;cur++;i1++;}else{cur--;i2++;}}cout << ret << endl;
}

?反向：

jiangly寫法：在所有對數中，減去不相交的數目。

Submission #53862212 - Tokio Marine & Nichido Fire Insurance Programming Contest 2024（AtCoder Beginner Contest 355)

?對于每個新邊，看前面有多少條邊不相交的，總數減去不相交的即可。

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int N;std::cin >> N;std::vector<int> l(N), r(N);for (int i = 0; i < N; i++) {std::cin >> l[i] >> r[i];}std::sort(l.begin(), l.end());std::sort(r.begin(), r.end());i64 ans = 1LL * N * (N - 1) / 2;for (int i = 0, j = 0; i < N; i++) {while (j < N && r[j] < l[i]) {j++;}ans -= j;}std::cout << ans << "\n";return 0;
}