#include #include #include #include using namespace std; //segment tree #define segL (1 << 20) int segT[segL * 2]; void init() { for (int i = 0;i < segL * 2;i++)segT[i] = 0; } int c2(int X) { int res = 0; int t = X; if (t == 0)t = segL; while (1) { if (t % 2 == 0) { t /= 2; res++; } else { break; } } return res; } void update(int idx, long long X) { int i = idx + segL; segT[i] = X; i /= 2; while (i >= 1) { segT[i] = segT[2 * i] + segT[2 * i + 1]; i /= 2; } } int getS(int L, int R) { int res = 0; int tL = L; while (tL != R) { int b = c2(tL); for (; b >= 0; b--) { if (tL + (1 << b) <= R) { int segIdx = (tL + segL) >> b; res += segT[segIdx]; tL += (1 << b); break; } } } return res; } // segment tree //無重複の数列に対して、転倒数を求める関数。 long long inversion(const vector V) { init(); long long res = 0; for (int i = 0;i < V.size();i++) { res += (long long)getS(V[i], segL); update(V[i], 1); } return res; } //端点が無重複の区間列に対して、包含関係をなす区間の組の数を求める関数。 long long count_included_relation(const vector L, const vector R) { init(); vector>V; for (int i = 0;i < L.size();i++) { V.push_back(make_pair(L[i], R[i])); } sort(V.begin(), V.end()); long long res = 0; for (int i = 0;i < V.size();i++) { res += (long long)getS(V[i].second, segL); update(V[i].second, 1); } return res; } int main() { int N; cin >> N; vectorL(N), R(N); setcheck_; bool ng_ = 0; for (int i = 0;i < N;i++) { cin >> L[i] >> R[i]; if (L[i] <= 0 || L[i] >= R[i] || 1'000'001 <= R[i])ng_ = 1; check_.insert(L[i]);check_.insert(R[i]); } if (check_.size() != 2 * N || ng_) {//制約違反検出 int tmptmp1 = 1; int tmptmp0 = 0; N = tmptmp1 / tmptmp0;//Run Time Errorさせる } long long ans = 0; ans += count_included_relation(L, R); ans += inversion(R); reverse(L.begin(), L.end()); ans += inversion(L); long long NC2 = ((long long)N * (long long)(N - 1))/(long long)2; ans -= NC2; ans /= (long long)2; cout << ans; return 0; }