#include #include #include using namespace std; typedef long long ll; struct Chord { int L, R; // ????????????? L < R }; // ???????????? class BIT { vector tree; int n; public: BIT(int size) : n(size), tree(size + 1, 0) {} void add(int idx, int delta) { while (idx <= n) { tree[idx] += delta; idx += idx & -idx; } } int sum(int idx) { int s = 0; while (idx > 0) { s += tree[idx]; idx -= idx & -idx; } return s; } int rangeSum(int l, int r) { if (l > r) return 0; return sum(r) - sum(l - 1); } }; int main() { int N, M; cin >> N >> M; vector chords(N); for (int i = 0; i < N; ++i) { int a, b; cin >> a >> b; if (a > b) swap(a, b); // ?? L < R chords[i].L = a; chords[i].R = b; } // ????? L ???? sort(chords.begin(), chords.end(), [](const Chord& c1, const Chord& c2) { return c1.L < c2.L; }); // ??????????????? vector Lvals(N); for (int i = 0; i < N; ++i) { Lvals[i] = chords[i].L; } // ???????? k_i?????? j ?? chords[j].L < chords[i].R vector k(N); for (int i = 0; i < N; ++i) { int R = chords[i].R; // ???????? R ?????? int pos = lower_bound(Lvals.begin(), Lvals.end(), R) - Lvals.begin(); k[i] = pos - 1; } // ??? R ??????????? (R, ????) vector> d; for (int i = 0; i < N; ++i) { d.emplace_back(chords[i].R, i); } sort(d.begin(), d.end(), [](const pair& p1, const pair& p2) { return p1.first > p2.first; // ?? }); BIT bit(N); ll ans = 0; for (auto& p : d) { int i = p.second; // ?????????? int k_i = k[i]; if (i < k_i) { // ???? (i, k_i] ???????? // ???????1???????j????j+1 int left = i + 2; // j = i+1 ???? i+2 int right = k_i + 1; // j = k_i ???? k_i+1 int cnt = bit.rangeSum(left, right); ans += cnt; } // ?????????? bit.add(i + 1, 1); } cout << ans << endl; return 0; }