ARC159D-LIS 2

· · 题解

首先题目都叫 LIS 了，显然可以试试 dp。

这题放在 D 是离谱的，赛时多亏第一眼不会 C 才开了这题（bushi

首先发现倘若一段之后能接上下一段，则接上一定优，不妨设计 f_i 表示以 r_i 结尾的 LIS 的长度。

转移则十分好办：

若 r_j<l_i ， f_i=f_j+r_i-l_i+1 。

若 r_j>l_i ， f_i=f_j+r_i-r_j 。

然后就发现可以线段树优化 dp。

代码如下：

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
#define md(a) a=(a%mod+mod)%mod
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
const int N=400005,inf=1e16;
int n,m,l[N],r[N],rl[N],rr[N],f[N],cnt,b[N];
struct S
{
    struct Seg{int l,r,dat;}tree[N*4];
    void pushup(int v){tree[v].dat=max(tree[v*2].dat,tree[v*2+1].dat);}
    void build(int v,int l,int r)
    {
        tree[v]={l,r,-inf};if(l==r)return ;
        int mid=l+r>>1;build(v*2,l,mid),build(v*2+1,mid+1,r);
    }
    void add(int v,int x,int d)
    {
        if(tree[v].l>x||tree[v].r<x)return ;
        if(tree[v].l==tree[v].r)return void(tree[v].dat=max(tree[v].dat,d));
        add(v*2,x,d),add(v*2+1,x,d),pushup(v);
    }
    int ask(int v,int l,int r)
    {
        if(tree[v].l>r||tree[v].r<l)return -inf;
        if(l<=tree[v].l&&tree[v].r<=r)return tree[v].dat;
        return max(ask(v*2,l,r),ask(v*2+1,l,r));
    }
}A,B;
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&l[i],&r[i]),b[++cnt]=l[i],b[++cnt]=r[i];
    sort(b+1,b+cnt+1),m=unique(b+1,b+cnt+1)-b-1;
    for(int i=1;i<=n;i++)rl[i]=lower_bound(b+1,b+m+1,l[i])-b;
    for(int i=1;i<=n;i++)rr[i]=lower_bound(b+1,b+m+1,r[i])-b;
    A.build(1,1,m),B.build(1,1,m);
    for(int i=1;i<=n;i++)
    {
        f[i]=r[i]-l[i]+1,f[i]=max(f[i],A.ask(1,1,rl[i]-1)+r[i]-l[i]+1);
        f[i]=max(f[i],B.ask(1,rl[i]+1,rr[i]-1)+r[i]),A.add(1,rr[i],f[i]),B.add(1,rr[i],f[i]-r[i]);
    }
    int ans=0;for(int i=1;i<=n;i++)ans=max(ans,f[i]);cout<<ans;
    return 0;
}