ARC159D-solution

· · 题解

PART 0

wtcl。

PART 1

给出 n 组数 l_i,r_i，求依次把 \forall j\in[l_i,r_i] 拼起来的序列的 LIS。

PART 2

首先，这是一道线段树优化 dp。

没错，就是 dp。

我们首先想朴素的 dp 方程。

考虑设 dp_i 表示以 r_i 为结尾的 LIS。

肯定是要枚举之前的 j 并尝试将当前这段区间加到区间 j 后面去。

那么就有两种情况：

这种情况就说明 r_j 的后一个数就是 l_i，所以整个区间 i 都可以接上去。

那么新加的长度就是区间 i 的长度。

dp_i=dp_j+(r_i-l_i+1)

这种情况就说明新加的是 r_j,r_j+1,....,r_i，区间 i 只有部分可以加上去。

那么新加的长度就是 r_j+1,....,r_i，即 r_i-r_j。

dp_i=dp_j+(r_i-r_j)

综上，dp_i=\max _{j=1}^{i-1}\begin{cases} dp_j+r_i-l_i+1(r_j<l_i)\\ dp_j-r_j+r_i(r_j\ge l_i)\end{cases}

但是这样做是 O(n^2) 的。

PART 3

我们考虑线段树优化。

根据上个式子，我们可以发现与 j 相关的有 dp_j,dp_j-r_j 两项。

所以我们可以用两棵下标为 r_j 的权值线段树维护 dp_j 与 dp_j-r_j。

这样我们每次只需要取出 1\to l_i-1 范围内最大的 dp_j 与 l_i\to r_i 范围内最大的 dp_j-r_j，加上后面那堆之后取个 \max 即可。

PART 4

需要离散化。

#include<bits/stdc++.h>
using namespace std;
#define N 200001
int z[N<<3][3],l[N],r[N];//val:离散化之后的r[i]
int n,m,i,j,k,s,now,ans,cnt;
vector<int> val;
//z[p][1]维护dp[j]
//z[p][2]维护dp[j]-r[j]
void make_tree(int p,int l,int r,int now)
{
    z[p][now]=-1e9;
    if(l==r)return;
    z[p][now]=0;
    int mid=(l+r)>>1;
    make_tree(p<<1,l,mid,now);
    make_tree(p<<1|1,mid+1,r,now);
    z[p][now]=max(z[p<<1][now],z[p<<1|1][now]);
}
void add(int p,int l,int r,int d,int to,int now)
{
    if(l==r)
    {
        z[p][now]=max(z[p][now],d);
        return;
    }
    int mid=(l+r)>>1;
    if(to>mid)add(p<<1|1,mid+1,r,d,to,now);
    else add(p<<1,l,mid,d,to,now);
    z[p][now]=max(z[p<<1][now],z[p<<1|1][now]);
}
int query(int p,int l,int r,int k,int s,int now)
{
    if(k<=l&&r<=s)return z[p][now];
    int mid=(l+r)>>1,ans=-1e9;
    if(k<=mid)ans=max(ans,query(p<<1,l,mid,k,s,now));
    if(s>mid)ans=max(ans,query(p<<1|1,mid+1,r,k,s,now));
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&l[i],&r[i]);
        val.push_back(l[i]);
        val.push_back(r[i]);//l[i],r[i]都需要离散化
    }
    val.push_back(0);
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    m=val.size();//离散化用了vector,其实可以用数组
    make_tree(1,1,m,1);
    make_tree(1,1,m,2);
    add(1,1,m,0,1,1);
    add(1,1,m,0,1,2);
    for(i=1;i<=n;i++)
    {
        k=lower_bound(val.begin(),val.end(),l[i])-val.begin()+1;
        s=lower_bound(val.begin(),val.end(),r[i])-val.begin()+1;//查询离散化之后的l[i],r[i]
        now=max(query(1,1,m,1,k-1,1)+r[i]-l[i]+1,query(1,1,m,k,s,2)+r[i]);
        ans=max(ans,now);//now即为当前的dp[i],只不过省略了dp数组
        add(1,1,m,now,s,1);
        add(1,1,m,now-r[i],s,2);
    }
    printf("%d",ans);
    return 0;
}