P6390 [COCI2007-2008#4] POKLON 题解

harmis_yz · 2023-09-01 15:07:47 · 题解

感谢 @\color{#AEF}{\texttt{Celestial Cyan}} 大神对我的骚扰帮助。

分析

一眼 DP。

对于求最大满足条件区间数，我们定义状态函数 \mathit{f}_{i} 表示在第 1 到 i 个区间中选择，且必选第 i 个区间能够得到的最大长度。有转移方程：\mathit{f}_{i}=\max\{f[j]|\mathit{a}_{j}\le\mathit{a}_{i} \land \mathit{b}_{j} \ge \mathit{b}_{i} \}+1。

可以得到 50 分的 O(n^2) 的代码：

for(re int i=1;i<=n;++i){
    f[i]=1;
    for(re int j=1;j<i;++j){
        if(a[i].l>=a[j].l&&a[j].r>=a[i].r){
            if(f[j]+1>f[i]) f[i]=f[j]+1,nxt[i]=j;
        }
    }
}

考虑优化 \mathit{f}_{i} 的转移。这个代码与 LIS 模板几乎一致，所以很显然的也可以使用树状数组优化。因为我们需要记录方案，所以树状数组存 2 维：价值与该价值对应的下标。

我们将 \mathit{a},\mathit{b} 用一个结构体存放，按第一维从小到大排序。可以得到：对于每一个 i，都有 1 \le j \le i,\mathit{a}_j \le \mathit{a}_i。这样我们就消除了区间左端点的影响。剩下的就用树状数组查询 \ge \mathit{b}_i 的最大的 {f}_j 的值与其下标。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define PII pair<int,int>
#define x first
#define y second
const int N=1e5+10,MAXN=1e6+10;
int n;
PII f[N],tr[MAXN];
struct node{
    int l,r;
}a[N];
stack<int> st;
int id,maxx;
il bool cmp(node a,node b){return (a.l!=b.l)?(a.l<b.l):(a.r>b.r);}
il void insert(int x,int y,int id){
    while(x){
        if(tr[x].x<y) tr[x].x=y,tr[x].y=id;
        x-=x&(-x);
    }
    return ;
}
il PII query(int x){
    PII ans;ans={0,0};
    while(x<=MAXN){
        if(ans.x<tr[x].x) ans.x=tr[x].x,ans.y=tr[x].y;
        x+=x&(-x);
    }
    ans.x++;return ans;
}
il void read(){
    scanf("%lld",&n);
    for(re int i=1;i<=n;++i) scanf("%lld%lld",&a[i].l,&a[i].r);
    sort(a+1,a+n+1,cmp);
    return ;
}
il void solve(){
    for(re int i=1;i<=n;++i) f[i]=query(a[i].r),insert(a[i].r,f[i].x,i);
    for(re int i=1;i<=n;++i){
        if(maxx<f[i].x) maxx=f[i].x,id=i;
    }
    while(id!=0) st.push(id),id=f[id].y;
    return ;
}
il void print(){
    printf("%lld\n",maxx);
    while(!st.empty()){
        int now=st.top();st.pop();
        printf("%lld %lld\n",a[now].l,a[now].r);
    }
    return ;
}
signed main(){
    read(),solve(),print();
    return 0;
}