bzoj千题计划316：bzoj3173: [Tjoi2013]最长上升子序列（二分+树状数组）

https://www.lydsy.com/JudgeOnline/problem.php?id=3173

插入的数是以递增的顺序插入的

这说明如果倒过来考虑，那么从最后一个插入的开始删除，不会对以某个数结尾的最长上升子序列产生影响

所以先原序列求出来，输出即可

还原原序列的方法：

可以用平衡树，dfs序就是原序列

嫌麻烦，不想写，所以树状数组

假设最后一个数是n，插入位置是y，

倒数第二个数是n-1，插入位置是x

那么y就是n的最终位置

如果y在x后面，那么x就是n-1的最终位置

如果y在x前面，那么x+1就是n-1的最终位置

所以如果倒序插入每个数，

若数m的插入位置为p，

数m的最终位置就是当前序列的第p个空位

这可以二分+树状数组确定数m的位置

注意求LIS时，求出的f[i] 时以i结尾的LIS

要求回答序列的LIS，所以要跟f[i-1]取大

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 100001

#define lowbit(x) x&-x

int n;

int p[N];

int c[N];

int a[N];

int dp[N],m;

int f[N];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void add(int pos,int x)

{

    while(pos<=n)

    {

        c[pos]+=x;

        pos+=lowbit(pos);

    }

}

int query(int x)

{

    int sum=;

    while(x)

    {

        sum+=c[x];

        x-=lowbit(x);

    }

    return sum;

}

int find(int x)

{

    int l=,r=n,mid,tmp;

    while(l<=r)

    {

        mid=l+r>>;

        if(mid-query(mid)>=x) tmp=mid,r=mid-;

        else l=mid+;

    }

    return tmp;

}

void init()

{

    read(n);

    for(int i=;i<=n;++i) read(p[i]);

    int pos;

    for(int i=n;i;--i)

    {

        pos=find(p[i]+);

        a[pos]=i;

        add(pos,);

    }

}

void pre_LIS()

{

    dp[m=]=a[];

    f[a[]]=;

    int pos;

    for(int i=;i<=n;++i)

    {

        if(a[i]>dp[m])

        {

            dp[++m]=a[i];

            f[a[i]]=m;

        }

        else

        {

            pos=lower_bound(dp+,dp+m+,a[i])-dp;

            if(a[i]<dp[pos]) dp[pos]=a[i];

            f[a[i]]=pos;

        }

    }

}

void solve()

{

    int now=;

    for(int i=;i<=n;++i)

    {

        now=max(now,f[i]);

        printf("%d\n",now);

    }

}

int main()

{

    init();

    pre_LIS();

    solve();

}

巴特西

bzoj千题计划316：bzoj3173: [Tjoi2013]最长上升子序列（二分+树状数组）

最新文章

热门文章