题意

题目链接。

给定 $n$ 行 01 串，其中有 $m$ 个区间为 $1$​。删除若干 01 串使剩余串美丽，若干条 01 串美丽当且仅当任意相邻两个 01 串至少有相同的一位均为 $1$。

$n,m\le 3\times {10}^5$。

解析

考虑记 $f_i$ 为以第 $i$ 串结尾的最长美丽串的长度。发现 $f_i=f_j+1,j\in [1,i)$ 当且仅当第 $i$ 串和 $j$ 串有相同位的 $1$​，发现离散化后串一共就只有 $6\times {10}^5$ 位，我们考虑将贡献打在 01 串的具体位上。

记 $f_{i,j}$ 为当前遍历到第 $i$ 个串，其中最后一个串的第 $j$ 位上为 $1$ 的最大贡献，容易发现 $i$ 实际没什么用。那么我们考虑对于 $j$ 建一棵线段树，遍历到第 $i$ 个串时，我们在线段树上查询第 $i$ 个串所有 $1$ 位置的答案并取最大值再加一作为以当前串结尾的答案，再用这个答案去更新该串的所有 $1$ 位置即可。

由于要输出方案，线段树改成 pair，分别存答案和产生这个答案的串即可。

代码

#include<bits/stdc++.h>
#define pi pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define ls x<<1
#define rs x<<1|1
using namespace std;
const int N=3e5+5;
pi tr[N<<3],tag[N<<3];
int n,m,pre[N],b[N<<1],cnt,mx;
int ans,ansp;
vector<pi> vec[N];
inline pi Max(pi x,pi y){
    if(x.fi>y.fi) return x;
    return y;
}
inline void pushdown(int x){
    if(!tag[x].fi) return;
    tr[ls]=tag[x],tr[rs]=tag[x];
    tag[ls]=tag[x],tag[rs]=tag[x];
    tag[x]=mk(0,0);
}
inline void pushup(int x){
    tr[x]=Max(tr[ls],tr[rs]);
}
inline pi query(int x,int l,int r,int L,int R){
    if(l>=L&&r<=R) return tr[x];
    int mid=(l+r)>>1;
    pushdown(x);
    if(L<=mid&&R>mid) return Max(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
    if(L<=mid) return query(ls,l,mid,L,R);
    return query(rs,mid+1,r,L,R);
}
inline void modify(int x,int l,int r,int L,int R,pi k){
    if(l>=L&&r<=R){tr[x]=k;tag[x]=k;return;}
    int mid=(l+r)>>1;
    pushdown(x);
    if(L<=mid) modify(ls,l,mid,L,R,k);
    if(R>mid) modify(rs,mid+1,r,L,R,k);
    pushup(x);
}
bool vis[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,l,r;i<=m;i++){
        scanf("%d%d%d",&x,&l,&r);
        vec[x].push_back(mk(l,r));
        b[++cnt]=l;b[++cnt]=r;
    }
    sort(b+1,b+1+cnt);
    cnt=unique(b+1,b+1+cnt)-b-1;
    for(int i=1;i<=n;i++){
        for(auto &x:vec[i]){
            x.fi=lower_bound(b+1,b+1+cnt,x.fi)-b;
            x.se=lower_bound(b+1,b+1+cnt,x.se)-b;
        }
    }//离散化
    for(int i=1;i<=n;i++){
        mx=-1;
        for(auto x:vec[i]){//求当前串的答案
            pi t=query(1,1,cnt,x.fi,x.se);
            if(t.fi>mx){mx=t.fi;pre[i]=t.se;}
        }
        if(mx+1>ans){//更新全局答案
            ans=mx+1;
            ansp=i;
        }
        for(auto x:vec[i]){//更新对应位置的答案
            pi t=mk(mx+1,i);
            modify(1,1,cnt,x.fi,x.se,t);
        }
    }
    printf("%d\n",n-ans);
    for(int i=ansp;i;i=pre[i]) vis[i]=1;
    for(int i=1;i<=n;i++){
        if(!vis[i]) printf("%d ",i);
    }
    return 0;
}

				

					
				
				

					
				
				

					
				
				

					
				
			

掉大分，哈哈。