[TJOI2013]最长上升子序列

题目

发现是顺次插入的，于是很好做

设\(dp_i\)表示\(i\)结尾的\(LIS\)，每次插入一个数找到之前的最大的\(dp_j\)加一就好了

至于如何找到这个元素应该在的位置，可以考虑类似区间提取的方法

如何要在\(x\)位置后面插入一个元素的话我们就先将\(x\)转到根，\(x+1\)转成根的右儿子，\(x+1\)的位置必然没有左儿子我们直接在这里插入就好了

不知道为什么我求第\(k\)小都能写错

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 100005
#define re register
#define inf 999999999
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{
    char c=getchar();int x=0;while(c<‘0‘||c>‘9‘) c=getchar();
    while(c>=‘0‘&&c<=‘9‘) x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int ch[maxn][2],fa[maxn],sz[maxn],g[maxn],mx[maxn];
int n,root,m;
inline void update(int x) {
    mx[x]=g[x];sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
    mx[x]=max(mx[x],mx[ch[x][0]]);
    mx[x]=max(mx[x],mx[ch[x][1]]);
    if(x==1||x==2) mx[x]=g[x]=0;
}
inline void rotate(int x) {
    int y=fa[x],z=fa[y],k=ch[y][1]==x,w=ch[x][k^1];
    ch[z][ch[z][1]==y]=x,ch[x][k^1]=y,ch[y][k]=w;
    update(y),update(x),fa[w]=y,fa[y]=x,fa[x]=z;
}
inline void splay(int x,int goal) {
    while(fa[x]!=goal) {
        int y=fa[x];
        if(fa[y]!=goal) rotate((ch[y][1]==x)^(ch[fa[y]][1]==y)?x:y);
        rotate(x);
    }
    if(!goal) root=x;
}
inline int find_rank(int x)
{
    int u=root;
    while(1) {
        if(sz[ch[u][0]]>=x) u=ch[u][0];
            else if(x>sz[ch[u][0]]+1) x-=sz[ch[u][0]]+1,u=ch[u][1];
                else return u;
    }
}
int main()
{
    scanf("%d",&n);
    root=1,sz[1]=2,fa[1]=0,ch[1][0]=2;
    sz[2]=1,fa[2]=1;m=2;
    int x;
    for(re int i=1;i<=n;i++)
    {
        scanf("%d",&x);x++;
        int aa=find_rank(x),bb=find_rank(x+1);
        splay(aa,0),splay(bb,aa);
        int t=ch[root][1];
        ch[t][0]=++m,fa[m]=t,sz[m]=1;
        splay(m,0);
        g[m]=mx[ch[root][0]]+1;update(m);
        printf("%d\n",mx[m]);
    }
    return 0;
}

[TJOI2013]最长上升子序列

原文：https://www.cnblogs.com/asuldb/p/10363236.html