#include using namespace std; using SS = int; class SegmentTree2D{ //二次元セグ木 計算量O(logH*logW) メモリO(2H+N). private: using Typepos = int; class DynamicSegmentTree{ //動的再帰セグ木 二分探索はない. public: SS op(SS a,SS b){return a+b;} static inline const SS e = 0; private: struct Node{ Typepos pos; //葉posの頂点. SS v,all; //v->posの値,all->部分木全部. Node *LR[2]; //二分木. Node(Typepos p,SS vv):pos(p),v(vv),all(vv),LR{nullptr,nullptr}{} }; Node *root; public: Typepos siz = 1<<30; DynamicSegmentTree(){root = nullptr;} void make(Typepos N){siz = 1; while(siz < N) siz *= 2;} void setsiz(Typepos N){assert(N==(N&-N)); siz = N;} private: SS getval(Node *p){return p?p->all:e;} //ノードpのallを返す. nullptrの場合分け省く用. //葉でない[a,b)の頂点にも[a,b)の1つを割り振ることにより空間をO(N)にする 適宜割り振る所は更新. Node* update(Typepos a,Typepos b,Typepos pos,Node *p,SS &v){ //p<-op(p,v); 更新する. if(p == nullptr) return new Node(pos,v); if(p->pos == pos){ p->v = op(p->v,v); p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1]))); return p; } Typepos m = (a+b)/2; if(pos < m){ if(pos > p->pos) swap(pos,p->pos),swap(v,p->v);//左の子のposは親のposより小さくする. p->LR[0] = update(a,m,pos,p->LR[0],v); } else{ if(pos < p->pos) swap(pos,p->pos),swap(v,p->v); //右の子は親より大きく. p->LR[1] = update(m,b,pos,p->LR[1],v); } p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1]))); return p; } Node* set(Typepos a,Typepos b,Typepos pos,Node *p,SS &v){ //p<-v 設定する. if(p == nullptr) return new Node(pos,v); if(p->pos == pos){ p->v = v; p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1]))); return p; } Typepos m = (a+b)/2; if(pos < m){ if(pos > p->pos) swap(pos,p->pos),swap(v,p->v); //左の子のposは親のposより小さくする. p->LR[0] = set(a,m,pos,p->LR[0],v); } else{ if(pos < p->pos) swap(pos,p->pos),swap(v,p->v); //右の子は親より大きく. p->LR[1] = set(m,b,pos,p->LR[1],v); } p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1]))); return p; } public: void update(Typepos pos,SS x){ assert(0 <= pos && pos < siz); root = update(0,siz,pos,root,x); } void set(Typepos pos,SS x){ assert(0 <= pos && pos < siz); root = set(0,siz,pos,root,x); } private: SS findans(Typepos L,Typepos R,Typepos a,Typepos b,Node *p){ if(p == nullptr || R <= a || b <= L) return e; if(L <= a && b <= R) return p->all; Typepos m = (a+b)/2; SS ret = findans(L,R,a,m,p->LR[0]); if(L <= p->pos && p->pos < R) ret = op(ret,p->v); return op(ret,findans(L,R,m,b,p->LR[1])); } public: SS rangeans(Typepos L,Typepos R){ assert(0 <= L && L <= siz && 0 <= R && R <= siz); // L>Rは許容する. if(L >= R) return e; return findans(L,R,0,siz,root); } SS allrange(){return getval(root);} SS get(Typepos pos){return rangeans(pos,pos+1);} //O(logsiz). }; int h = 1; Typepos w = 1; vector dat; public: SegmentTree2D(int H,Typepos W){ h = 1,w = 1; while(h < H) h <<= 1; while(w < W) w <<= 1; dat.resize(h*2); for(auto &d : dat) d.setsiz(w); } void update(int x,Typepos y,SS v){ //(x,y)にvを加える. assert(0 <= x && x < h && 0 <= y && y < w); x += h; while(x > 0) dat.at(x).update(y,v),x >>= 1; } void set(int x,Typepos y,SS v){ //(x,y)をvにする. assert(0 <= x && x < h && 0 <= y && y < w); x += h; while(x > 0) dat.at(x).set(y,v),x >>= 1; } SS rangeans(int x1,int x2,Typepos y1,Typepos y2){ //(x1,y1)~(x2,y2)の区間の総和. assert(0 <= min(x1,x2) && max(x1,x2) <= h && 0 <= min(y1,y2) && max(y1,y2) <= w); //x1>x2,y1>y2はok. x1 += h,x2 += h; SS ret = dat.at(0).e; while(x1 < x2){ if(x1&1) ret = dat.at(0).op(ret,dat.at(x1++).rangeans(y1,y2)); if(x2&1) ret = dat.at(0).op(dat.at(--x2).rangeans(y1,y2),ret); x1 >>= 1; x2 >>= 1; } return ret; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; SegmentTree2D Z(1000000,1000000); vector> LR(N); for(auto &[l,r] : LR) cin >> l >> r,l--; long long answer = 0; for(int i=N; i--;){ auto [l,r] = LR.at(i); answer += Z.rangeans(l,r,l,r); Z.update(l,r,1); } cout << answer << endl; }