#include using namespace std; using Int = long long; using T = Int; struct BinaryIndexedTree { vector< T > data; BinaryIndexedTree(Int sz) { data.assign(++sz, 0); } T sum(Int k) { T ret = 0; for(++k; k > 0; k -= k & -k) ret += data[k]; return (ret); } void add(Int k, T x) { for(++k; k < data.size(); k += k & -k) data[k] += x; } }; struct SegmentTreeBIT { Int sz; vector< BinaryIndexedTree > seg; vector< vector< Int > > beet; SegmentTreeBIT(Int n) { sz = 1; while(sz < n) sz <<= 1; beet.resize(2 * sz - 1); } void update(Int x, Int y, Int z) { x += sz - 1; seg[x].add(lower_bound(begin(beet[x]), end(beet[x]), y) - begin(beet[x]), z); while(x > 0) { x = (x - 1) >> 1; seg[x].add(lower_bound(begin(beet[x]), end(beet[x]), y) - begin(beet[x]), z); } } void build() { for(Int k = beet.size() - 1; k >= 0; k--) { sort(begin(beet[k]), end(beet[k])); beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k])); } for(Int k = 0; k < beet.size(); k++) { seg.emplace_back(BinaryIndexedTree(beet[k].size())); } } Int query(Int a, Int b, Int x, Int y, Int k, Int l, Int r) { if(a >= r || b <= l) return (0); if(a <= l && r <= b) { Int p = y, q = x; y = lower_bound(begin(beet[k]), end(beet[k]), y) - begin(beet[k]); x = lower_bound(begin(beet[k]), end(beet[k]), x) - begin(beet[k]); return (seg[k].sum(y) - seg[k].sum(x)); } return (query(a, b, x, y, 2 * k + 1, l, (l + r) >> 1) + query(a, b, x, y, 2 * k + 2, (l + r) >> 1, r)); } Int query(Int a, Int b, Int x, Int y) { return (query(a, b, x, y, 0, 0, sz)); } void preupdate(Int x, Int y) { x += sz - 1; beet[x].push_back(y); while(x > 0) { x = (x - 1) >> 1; beet[x].push_back(y); } } void prequery(Int a, Int b, Int x, Int y, Int k, Int l, Int r) { if(a >= r || b <= l) return; if(a <= l && r <= b) { beet[k].push_back(y); beet[k].push_back(x); return; } prequery(a, b, x, y, 2 * k + 1, l, (l + r) >> 1); prequery(a, b, x, y, 2 * k + 2, (l + r) >> 1, r); } void prequery(Int a, Int b, Int x, Int y) { prequery(a, b, x, y, 0, 0, sz); } }; //INSERT ABOVE HERE signed main(){ Int n,m; scanf("%lld %lld",&n,&m); vector a(n),b(n); for(Int i=0;ib[i]) swap(a[i],b[i]); seg.prequery(0,a[i],a[i],b[i]); seg.prequery(a[i],b[i],b[i],m); seg.preupdate(a[i],b[i]); } seg.build(); long long ans=0; for(Int i=0;ib[i]) swap(a[i],b[i]); ans+=seg.query(0,a[i],a[i],b[i]); ans+=seg.query(a[i],b[i],b[i],m); seg.update(a[i],b[i],1); } printf("%lld\n",ans); return 0; }