【BZOJ3173】[Tjoi2013]最长上升子序列

2015.08.12 10:49 Wed | 35次阅读 | 旧日oi | 固定链接 | 源码

Description

给定一个序列,初始为空。现在我们将1到N的数字插入到序列中,每次将一个数字插入到一个特定的位置。每插入一个数字,我们都想知道此时最长上升子序列长度是多少?

题解

在treap上打个标记就行了,或者离线处理按照普通的lis做。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100005
#define ls l[x]
#define rs r[x]
int n,cnt,root;
int mx[N],val[N],rnd[N],l[N],r[N],siz[N];
void update(int x)
{
    mx[x]=max(max(mx[ls],mx[rs]),val[x]);
    siz[x]=siz[ls]+siz[rs]+1;
}
void lturn(int &k)
{
    int t=r[k];r[k]=l[t];l[t]=k;
    siz[t]=siz[k];update(k);update(t);k=t;
}
void rturn(int &k)
{
    int t=l[k];l[k]=r[t];r[t]=k;
    siz[t]=siz[k];update(k);update(t);k=t;
}
void insert(int &x,int k,int maxx)
{
    if(!x)
    {
        x=++cnt;
        rnd[x]=rand();
        siz[x]=1;
        val[x]=mx[x]=maxx;
        return;
    }
    siz[x]++;
    if(siz[ls]>=k) 
    {
        insert(ls,k,maxx);
        if(rnd[ls]<rnd[x]) rturn(x);
    }
    else
    {
        insert(rs,k-siz[ls]-1,max(maxx,max(mx[ls],val[x])+1));
        if(rnd[rs]<rnd[x]) lturn(x);
    }
    mx[x]=max(max(mx[ls],mx[rs]),val[x]);
}
int main()
{
    cin>>n;
    for(int x,i=1;i<=n;i++)
    {
        scanf("%d",&x);
        insert(root,x,1);
        printf("%d\n",mx[root]);
    }
}```