#define PROBLEM "https://yukicoder.me/problems/2063" #include using namespace std; #define call_from_test #ifndef call_from_test #include using namespace std; #endif //BEGIN CUT HERE template struct RangeCount{ struct BIT{ vector dat; BIT(){} BIT(int n){dat.assign(++n,0);} T sum(int k){ T res=0; for(;k;k-=k&-k) res+=dat[k]; return res; } void add(int k,T v){ for(++k;k<(int)dat.size();k+=k&-k) dat[k]+=v; } }; int n; vector< vector > val; vector dat; RangeCount(){} RangeCount(int n):n(n){ val.assign(n<<1,vector()); dat.reserve(n<<1); } void preupdate(int a,Key x){ a+=n; while(a){ val[a].emplace_back(x); a>>=1; } } void build(){ for(int i=0;i>=1; } } T calc(int k,Key x,Key y){ auto &vs=val[k]; int p=lower_bound(vs.begin(),vs.end(),x)-vs.begin(); int q=lower_bound(vs.begin(),vs.end(),y)-vs.begin(); return dat[k].sum(q)-dat[k].sum(p); } // [a, b) * [x, y) T query(int a,int b,Key x,Key y){ T res=0; for(int l=a+n,r=b+n;l>=1,r>>=1){ if(l&1) res+=calc(l++,x,y); if(r&1) res+=calc(--r,x,y); } return res; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE //END CUT HERE signed main(){ return 0; } #endif #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); const char newl = '\n'; int n,m; cin>>n>>m; vector as(n),bs(n); for(int i=0;i>as[i]>>bs[i]; RangeCount seg(m); for(int i=0;ibs[i]) swap(as[i],bs[i]); seg.preupdate(as[i],bs[i]); } seg.build(); long long ans=0; for(int i=0;i