YbtOJ 644「平衡树」模糊序列

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
    Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));x*=f;}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
    Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);}
    Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=3e5+10,inf=2e9;
int n,Ans,rt;
class Treap{
    private:
        int cnt;struct node{int v,tg,rd,l,r;}T[N<<1];
        #define AP(x,sv) (T[x].tg+=sv,T[x].v+=sv)
        I void PD(CI x){T[x].l&&(AP(T[x].l,T[x].tg),0),T[x].r&&(AP(T[x].r,T[x].tg),0),T[x].tg=0;}
    public:
        I int NW(CI x){return T[++cnt]=(node){x,0,rand(),0,0},cnt;}
        I int M(CI x,CI y){if(!x!y) return x+y;if(T[x].rd>T[y].rd) return PD(x),T[x].r=M(T[x].r,y),x;else return PD(y),T[y].l=M(x,T[y].l),y;}
        I void S(RI z,CI v,int& x,int& y){if(!z) return void(x=y=0);if(PD(z),T[z].v<=v) x=z,S(T[z].r,v,T[z].r,y);else y=z,S(T[z].l,v,x,T[z].l);}
        I int C(RI x){if(!x) return 0;if(PD(x),!T[x].l){RI o=T[x].r;T[x].r=0;return o;}return T[x].l=C(T[x].l),x;}
        I void F(CI x){if(!x) return ;if(T[x].v<inf) Ans++;PD(x),F(T[x].l),F(T[x].r);}
        I void A(CI x){AP(x,1);}
}T;
int main(){
    freopen("vague.in","r",stdin),freopen("vague.out","w",stdout);
    RI i,o,x,y,z,l,r;for(srand(19260817),read(n),rt=T.NW(0),i=1;i<=n+1;i++) T.M(rt,T.NW(inf));
    for(i=1;i<=n;i++) read(l,r),T.S(rt,l-1,x,y),T.S(y,r-1,y,z),o=T.NW(l),y&&(T.A(y),0),z=T.C(z),rt=T.M(T.M(x,o),T.M(y,z));
    return T.F(rt),writeln(Ans-1),clear(),0;
}