YbtOJ 644「平衡树」模糊序列
题目链接：YbtOJ #644
小 A 有一个长度为 n 的正整数序列 a_{1sim n}，但其中所有的值都已经模糊不清了，只知道每个数的取值范围。
即，对于每个 iin[1,n]，给出两个正整数 l_i,r_i，表示 a_iin[l_i,r_i]。
对于所有可能的序列，他想要求出 最长严格上升子序列长度 的最大值。
1le nle3times10^5，1le l_ile r_ile10^9。
Solution
设 f_i 表示长度为 i 的严格上升子序列最后一位的最小值。显然随着 i 的增大，f_i 必递增。
分类讨论转移。
可以用平衡树实现这一过程。最终的答案就是平衡树的大小。
时间复杂度：O(nlog n)。
Code
代码语言：javascript复制#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 48,x/=10);W(OT) pc(OS[OT--]);}
Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[ OT]=x 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;
}
