【Codeforces 809D】Hitchhiking in the Baltic States | Mrsrz's blog

平衡树优化DP

题目大意：

给定 $n$ 个数，第 $i$ 个数可以选 $[l_i,r_i]$ 中的任意整数。现在要确定每个数，使得最长严格上升子序列长度最大。求最大长度。

题解：

思考原来用单调队列求 LIS 的做法，令 $f_i$ 表示当前长度为 $i$ 的上升子序列中，结尾能取到的最小值。

这个单调队列 $f$ 满足 $\forall i\in[1,m),f_i < f_{i+1}$。

我们对一个新的数 $l,r$，考虑其对 $f$ 的影响。

我们把 $f$ 分为三个部分 $x_1,y_1;x_2,y_2;x_3,y_3$：

1. $\forall i\in[x_1,y_1],f_i < l$，那么只有 $f_{y_1}$ 后面加上新的数 $l$ 能产生贡献（$f_{y_1+1}\geq l$）。令新的 $f_{y_1+1}=l$。
2. $\forall i\in[x_2,y_2],l\leq f_i<r$。那么对于 $f_i$，显然可以在其后面加一个 $f_{i}+1$ 让其答案更长。由于 $f_{i}+1\leq f_{i+1}$，所以相当于把这段整体加一后向右平移了一格。
3. $\forall i\in[x_3,y_3],f_i\geq r$，这里的每个位置都无法产生新的贡献。

那么，我们可以用平衡树来维护这个单调队列。每次新插入一个数时，把平衡树分成这三个部分。对第一部分，在末尾插入 $l$，对于第二部分，打整体加一的标记，对于第三部分，如果有元素则删掉第一个元素（被第二部分平移过来的元素或者被第一部分新添加的元素覆盖原有贡献）。再把三部分合并即可。

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

就喜欢写只旋到根的 Splay

Code：

#include<iostream>
using namespace std;
const int N=3e5+6;
int ch[N][2],fa[N],rt,nod,sz[N],val[N],tag[N],mx[N];
int n;
inline int ckr(int x,int k=1){return ch[fa[x]][k]==x;}
inline void add(int x,int dlt){tag[x]+=dlt,val[x]+=dlt,mx[x]+=dlt;}
inline void pushdown(int o){
    if(tag[o]){
        if(ch[o][0])add(ch[o][0],tag[o]);
        if(ch[o][1])add(ch[o][1],tag[o]);
        tag[o]=0;
    }
}
inline void update(int x){
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
    mx[x]=max(val[x],mx[ch[x][1]]);
}
void rotate(int x){
    int y=fa[x],z=fa[y],k=ckr(x);
    if(z)ch[z][ckr(y)]=x;
    fa[x]=z,fa[y]=x,fa[ch[x][!k]]=y;
    ch[y][k]=ch[x][!k],ch[x][!k]=y;update(y);
}
void splay(int x){
    static int sta[N],top;sta[top=1]=x;
    for(int y=x;fa[y];sta[++top]=y=fa[y]);
    while(top)pushdown(sta[top--]);
    for(;fa[x];rotate(x))
        if(fa[fa[x]])rotate((ckr(x)^ckr(fa[x]))?x:fa[x]);
    update(x);
}
int find(int x,int k){
    if(!x||mx[x]<k)return 0;
    while(1){
        pushdown(x);
        if(val[x]<k)x=ch[x][1];else
        if(ch[x][0]&&mx[ch[x][0]]>=k)x=ch[x][0];else{
            splay(x);
            return x;
        }
    }    
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    rt=nod=1;
    sz[1]=1;
    for(int i=1;i<=n;++i){
        int l,r;
        cin>>l>>r;
        int Left,Mid,Right;
        Mid=find(rt,l);
        if(Mid==0){
            ++nod;
            sz[nod]=1,val[nod]=mx[nod]=l;
            ch[nod][0]=rt,fa[rt]=nod;
            update(nod);
            rt=nod;
            continue;
        }
        Left=ch[Mid][0];if(Left)ch[Mid][0]=fa[Left]=0,update(Mid);
        Right=find(Mid,r);
        if(Right)Mid=ch[Right][0],ch[Right][0]=fa[Mid]=0,update(Right);
        if(Mid)add(Mid,1);
        if(Right)Right=ch[Right][1],fa[Right]=0;
        if(Right){
            if(Mid){
                while(ch[Right][0])Right=ch[Right][0];
                splay(Right);
                fa[Mid]=Right,ch[Right][0]=Mid,update(Right);
            }
            Mid=Right;
        }
        ++nod;
        sz[nod]=1,val[nod]=mx[nod]=l;
        ch[nod][0]=Left,ch[nod][1]=Mid;
        fa[Left]=fa[Mid]=nod;
        update(nod);
        rt=nod;
    }
    cout<<sz[rt]-1<<'\n';
    return 0;
}