AT_arc159_d [ARC159D] LIS 2 题解

toolong114514 · 2024-07-09 18:33:08 · 题解

AT_arc159_d [ARC159D] LIS 2 题解

以前机房某场模拟赛的 T3，因为 dp 转移写得太狗屎赛时没调出正解。

题面大意

传送门。

解题思路

定义 f_i 为以第 i 个单调递增段的最右端为结尾的最长上升子序列长度。

容易发现最优解的结尾一定是某个单调递增段的最右端，否则我们可以继续往后面填数，答案一定不优。

接下来考虑转移的方式。

只有右端点比当前段右端点小才能转移。

转移的类型又分为两种：

• 两个区间没有交集，直接加上当前区间长
• 两个区间有交集，加上二者右端点之差。

我们现在可以愉快地写出转移方程了：

（特别地，我们规定 f_0=l_0=r_0=0）

最后答案就是对所有 f_i 取 \max。

直接朴素转移是 O(n^2) 的，无法通过 n\le2\times10^5 的数据，考虑线段树优化。

开两颗权值线段树，一颗维护 f_i 的最大值，另一颗维护 f_i-r_i 的最大值，每求出一个 f_i 就以 r_i 为下标插入线段树中，求 f_i 时根据 r_i 和转移方程查询即可。

还有些设最小值之类的细节问题，注意一下就行。

时间复杂度约为 O(n\log n)，可以通过本题。

代码很好写。

参考代码

#include<iostream>
using namespace std;
#define int long long
const int INF=0x7fffffffffffffff;
const int LIM=1e9;
const int N=2e6+10;
struct node{
    int ln,rn;
}a[N];
int f[N];
int n,ans;
struct ccf{
    int lson,rson,maxn;
}tree1[4*N],tree2[4*N];
int root1,root2,tmr1,tmr2;
void push_up1(int pos){
    tree1[pos].maxn=max(tree1[tree1[pos].lson].maxn,tree1[tree1[pos].rson].maxn);
}
void upd1(int &pos,int l,int r,int dot,int x){
    if(!pos) pos=++tmr1;
    if(l==r){
        tree1[pos].maxn=x;
        return;
    }
    int mid=(l+r)/2;
    if(dot<=mid) upd1(tree1[pos].lson,l,mid,dot,x);
    else upd1(tree1[pos].rson,mid+1,r,dot,x);
    push_up1(pos);
}
int ask1(int pos,int l,int r,int lft,int rgt){
    if(lft>rgt||!pos||rgt<l||r<lft) return 0;
    if(lft<=l&&r<=rgt) return tree1[pos].maxn;
    int mid=(l+r)/2;
    return max(ask1(tree1[pos].lson,l,mid,lft,rgt),ask1(tree1[pos].rson,mid+1,r,lft,rgt));
}
void push_up2(int pos){
    tree2[pos].maxn=max(tree2[tree2[pos].lson].maxn,tree2[tree2[pos].rson].maxn);
}
void upd2(int &pos,int l,int r,int dot,int x){
    if(!pos) pos=++tmr2;
    if(l==r){
        tree2[pos].maxn=x;
        return;
    }
    int mid=(l+r)/2;
    if(dot<=mid) upd2(tree2[pos].lson,l,mid,dot,x);
    else upd2(tree2[pos].rson,mid+1,r,dot,x);
    push_up2(pos);
}
int ask2(int pos,int l,int r,int lft,int rgt){
    if(!pos||rgt<l||r<lft) return -INF;
    if(lft<=l&&r<=rgt) return tree2[pos].maxn;
    int mid=(l+r)/2;
    return max(ask2(tree2[pos].lson,l,mid,lft,rgt),ask2(tree2[pos].rson,mid+1,r,lft,rgt));
}
signed main(){
    ios::sync_with_stdio(false);
    tree2[0].maxn=-INF;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].ln>>a[i].rn;
    }
    for(int i=1;i<=n;i++){
        f[i]=max(ask1(root1,1,LIM,1,a[i].ln-1)+a[i].rn-a[i].ln+1,ask2(root2,1,LIM,a[i].ln,a[i].rn-1)+a[i].rn);
        upd1(root1,1,LIM,a[i].rn,f[i]);
        upd2(root2,1,LIM,a[i].rn,f[i]-a[i].rn);
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,f[i]);
    }
    cout<<ans<<endl;
    return 0;
}

本代码可以通过 AT 的评测。

Written by toolong114514 on 2024/7/9.