树状数组求LIS

· · 题解

题目AT2827 LIS

大家都用dp写的

但是我dp太菜

于是写了个树状数组

代码都在注释里 注释都在代码里

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int rd(){
    int x=0,fl=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fl=-fl;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*fl;
}
int n,b[100100],a[100100];
ll c[100100],f[100100];
void upd(int x,ll v){
    for(;x<=n;x+=x&-x)
        c[x]=max(c[x],v);                          //前x个数中的维护最大值
}
ll ask(int x){
    ll cnt=0;
    for(;x>=1;x-=x&-x)
        cnt=max(cnt,c[x]);
    return cnt;
}
void init(){
    n=rd();ll ans=0;
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)b[i]=a[i]=rd();
    sort(b+1,b+n+1);
    unique(b+1,b+n+1);
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+n+1,a[i])-b;//离散化，这题好像用不到...
}
void work(){
    for(int i=1;i<=n;i++){
        f[i]=ask(a[i])+1;                             //每次更新最大值
        upd(a[i],f[i]);
    }
}
void outt(){
    ll ans=1;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i]);
    printf("%lld",ans);
}
int main(){
    init();
    work();
    outt();
    return 0;
}

是不是感觉有点玄学

这里给出一个证明 可惜Lougu太小我写不下

举一个简单的栗子：

对于 1 4 2 3 5这个序列

显然他的LIS是4也就是 1 2 3 5

然后我们设 f[i]表示以a[i]结尾的LIS

有f[i]=max{f[j]+1 | j<i&&a[i]<a[j]};(这个写成集合的形式应该能懂吧

很显然可以使用树状数组优化

由于插入n次，每次询问代价是logn

总复杂的就是O(nlogn).

emmm...

还没看懂？

上图！

首先我们先把1放入树状数组

发现1前并无数或者说f[0]=0;

则将f[1]赋值为f[0]+1=1，且树状数组中1位置赋值为1；

然后插入4

发现4前fmax=f[1]=1;

则将f[4]赋值为f[1]+1=2，且树状数组中4位置赋值为2； ：

然后插入2

发现2前fmax=f[1]=1;

则将f[2]赋值为f[1]+1=2，且树状数组中2位置赋值为2；

然后插入3

发现3前fmax=f[2]=2;

则将f[3]赋值为f[2]+1=3，且树状数组中3位置赋值为3；

然后插入5

发现5前fmax=f[3]=3;

则将f[5]赋值为f[3]+1=4，且树状数组中5位置赋值为4；

emmmm

差不多了吧 附上精简版代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,x,b[100100],a[100100];
ll c[100100],f[100100];
void upd(int x,ll v){
    for(;x<=n;x+=x&-x)
        c[x]=max(c[x],v);
}
ll ask(int x){
    ll cnt=0;
    for(;x>=1;x-=x&-x)
        cnt=max(cnt,c[x]);
    return cnt;
}

int main(){
    scanf("%d",&n);
    ll ans=0;
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        f[i]=ask(x)+1;
        upd(x,f[i]);
    }

    for(int i=1;i<=n;i++)
        ans=max(ans,f[i]);
    printf("%lld",ans);

    return 0;
}