YbtOJ 644「平衡树」模糊序列

(Updated: )
oi
, ,

题目链接：YbtOJ #644

小 A 有一个长度为 $n$ 的正整数序列 $a_{1\sim n}$，但其中所有的值都已经模糊不清了，只知道每个数的取值范围。

即，对于每个 $i\in[1,n]$，给出两个正整数 $l_i,r_i$，表示 $a_i\in[l_i,r_i]$。

对于所有可能的序列，他想要求出 最长严格上升子序列长度 的最大值。

$1\le n\le3\times10^5$，$1\le l_i\le r_i\le10^9$。

Solution

设 $f_i$ 表示长度为 $i$ 的严格上升子序列最后一位的最小值。显然随着 $i$ 的增大，$f_i$ 必递增。

那么我们可以针对每次新增的数 $x\in[l,r]$ 分类讨论转移。
$$
f_{i-1}<l-1,f_i=\min {f_i, l}\\
l-1\leq f_{i-1}\leq r-1, f_i = \min { f_i,f_{i-1}+1 }
$$
发现等价于在第 $p$ 位插入一个新数 $l$，将原本的 $[p,q]$ 部分右移一位并加 $1$，删去原本的第 $q+1$ 位。

可以用平衡树实现这一过程。最终的答案就是平衡树的大小。

时间复杂度：$O(n\log n)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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;
}