#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int ll; typedef pair P; random_device rnd; mt19937 mt(rnd()); uniform_real_distribution<> rnd1(0, 1.0); struct node_t{ int val; node_t *lch; node_t *rch; double pri; int cnt; int lazy_val; bool lazy; node_t() {} node_t(int v, double p):val(v), pri(p), cnt(1), lazy_val(0), lazy(false), lch(nullptr), rch(nullptr){} }; int count(node_t *t){ return !t ? 0 : t->cnt; } void push(node_t *t){ if(!t) return; if(t->lazy){ t->val+=t->lazy_val; if(t->lch){ t->lch->lazy=true; t->lch->lazy_val+=t->lazy_val; } if(t->rch){ t->rch->lazy=true; t->rch->lazy_val+=t->lazy_val; } t->lazy_val=0; t->lazy=false; } } node_t *update(node_t *t){ push(t); push(t->lch); push(t->rch); t->cnt=count(t->lch)+count(t->rch)+1; return t; } node_t *merge(node_t *l, node_t *r){ if(!l || !r) return !l ? r : l; update(l); update(r); if(l->pri > r->pri){ l->rch=merge(l->rch, r); return update(l); }else{ r->lch=merge(l, r->lch); return update(r); } } pair split(node_t *t, int v){ //[0, v), [v, inf) if(!t) return make_pair(nullptr, nullptr); update(t); if(v <= t->val){ pair s=split(t->lch, v); t->lch=s.second; return make_pair(s.first, update(t)); }else{ pair s=split(t->rch, v); t->rch=s.first; return make_pair(update(t), s.second); } } pair split2(node_t *t, int k){ //[0, k), [k,n) if(!t) return make_pair(nullptr, nullptr); update(t); if(k <= count(t->lch)){ pair s=split2(t->lch, k); t->lch=s.second; return make_pair(s.first, update(t)); }else{ pair s=split2(t->rch, k-1-count(t->lch)); t->rch=s.first; return make_pair(update(t), s.second); } } node_t *query(node_t *t, int l, int r){ pair s=split(t, l); pair s2=split(s.second, r); if(s2.first){ s2.first->lazy=true; s2.first->lazy_val=1; } pair s3=split2(s2.second, 1); return merge(s.first, merge(new node_t(l, rnd1(mt)), merge(s2.first, s3.second))); } int main() { int n; cin>>n; node_t *s=nullptr; for(int i=0; i>l>>r; s=query(s, l, r); } cout<