#include using namespace std; using Int = signed; 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 < (Int)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.assign(2 * sz, vector()); } void update(Int x, Int y, Int z) { x += sz; while(x) { seg[x].add(lower_bound(begin(beet[x]), end(beet[x]), y) - begin(beet[x]), z); //Int k=lower_bound(begin(beet[x]), end(beet[x]), y) - begin(beet[x]); //assert(beet[x][k]==y); x>>=1; } } void build() { seg.reserve(sz * 2); for(Int k = 0; k < sz * 2; k++) { sort(begin(beet[k]), end(beet[k])); beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k])); seg.emplace_back(BinaryIndexedTree(beet[k].size())); } } inline Int query(Int k,Int x,Int y){ Int p = lower_bound(begin(beet[k]), end(beet[k]), y) - begin(beet[k]); Int q = lower_bound(begin(beet[k]), end(beet[k]), x) - begin(beet[k]); //assert(beet[k][p]==y); //assert(beet[k][q]==x); return (seg[k].sum(p) - seg[k].sum(q)); } Int query(Int a, Int b, Int x, Int y) { Int res=0; for(Int l=a+sz,r=b+sz;l>=1,r>>=1){ if(l&1) res+=query(l++,x,y); if(r&1) res+=query(--r,x,y); } return res; } void prequery(Int a, Int b, Int x, Int y) { for(Int l=a+sz,r=b+sz;l>=1,r>>=1){ if(l&1) beet[l].emplace_back(x),beet[l].emplace_back(y),l++; if(r&1) r--,beet[r].emplace_back(x),beet[r].emplace_back(y); } } void preupdate(Int x, Int y) { x += sz; while(x) { beet[x].push_back(y); x>>=1; } } }; //INSERT ABOVE HERE signed main(){ Int n,m; scanf("%d %d",&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(); exit(0); long long ans=0; for(Int i=0;i