#include #include #include using namespace std; #define INF 100000000 #define YJ 1145141919 #define INF_INT_MAX 2147483647 #define INF_LL_MAX 9223372036854775807 #define EPS 1e-10 #define MOD 1000000007 #define Pi acos(-1) #define LL long long #define ULL unsigned long long #define LD long double #define int long long const int MAX_N = 100005; const int MAX_M = 200005; int N, M; class Range { public: int a, b; bool operator < (const Range& r) const { return a < r.a; } }rangeList[MAX_N]; class Node { public: Node(LL v = unitValue) : value(v) { } Node operator + (const Node& monoid) const { return Node(this->getValue() + monoid.getValue()); } static Node unit() { return Node(unitValue); } void setValue(LL l) { this->value = l; } LL getValue() const { return this->value; } private: LL value; static const LL unitValue = 0; }; template class SegmentTree { public: SegmentTree(int size) { init(size); } void init(int size) { vec.clear(); k = 1; while(k < size) { k *= 2; } for(int i = 0; i < 2*k; i++) { vec.push_back(T::unit()); } } void update(int i, T x) { //iをxに変更する i += k-1; vec[i] = x; while(i > 0) { i = (i-1)/2; vec[i] = vec[i*2+1] + vec[i*2+2]; } } T find(int l, int r) { return _find(l, r, 0, 0, k); } private: vector vec; int k; T _find(int l, int r, int k, int x, int y) { if (r <= x || y <= l) { //重なってない場合 return T::unit(); } else if (l <= x && y <= r) { //完全にかぶってる場合 return vec[k]; } else { //中途半端にかぶってる場合 int mid = (x+y)/2; T lNode = _find(l, r, 2*k+1, x, mid); T rNode = _find(l, r, 2*k+2, mid, y); return lNode + rNode; } } }; signed main() { cin >> N >> M; for(int i = 0; i < N; i++) { cin >> rangeList[i].a >> rangeList[i].b; if(rangeList[i].a > rangeList[i].b) { swap(rangeList[i].a, rangeList[i].b); } } sort(rangeList, rangeList + N); SegmentTree segmentTree(MAX_M); int ans = 0; for(int i = 0; i < N; i++) { ans += segmentTree.find(rangeList[i].a, rangeList[i].b+1).getValue(); segmentTree.update(rangeList[i].b, 1); } cout << ans << endl; return 0; }