思路

线段树优化

表示线段能组成漂亮序列最多的行数。那么每次转移的时候，区间上查找与线段对应位有的所有线段，选取最大的一个线段，那么。

考虑用线段树去优化，区间上找最大的，然后得到，接着用覆盖线段的区间。因为这个只和上一个状态有关，所以可以直接覆盖。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+7;
pair<int,int>t[maxn<<3],ac;
bool re[maxn<<3];
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline void pushup(int rt) {
    if(re[rt]) {
        t[rt<<1]=t[rt<<1|1]=t[rt];
        re[rt<<1]=re[rt<<1|1]=1;
        re[rt]=0;
    }
}
inline void update(int l,int r,int rt,int x,int y) {
    if(x<=l&&r<=y) {
        t[rt]=ac; re[rt]=1;
        return;
    }
    pushup(rt);
    int mid=(l+r)/2;
    if(x<=mid) update(lson,x,y);
    if(y>mid) update(rson,x,y);
    t[rt]=max(t[rt<<1],t[rt<<1|1]);
}
inline pair<int,int>query(int l,int r,int rt,int x,int y) {
    if(x<=l&&r<=y) return t[rt];
    pushup(rt);
    int mid=(l+r)/2;
    if(y<=mid) return query(lson,x,y);
    else if(x>mid) return query(rson,x,y);
    else return max(query(lson,x,y),query(rson,x,y)); 
}
vector<pair<int,int> >g[maxn];
int b[maxn<<1],tot,last[maxn];
bool vis[maxn];
int main() {
    cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1,row,x,y;i<=m;++i) {
        cin>>row>>x>>y;
        g[row].emplace_back(x,y);
        b[++tot]=x; b[++tot]=y;
    }
    sort(b+1,b+1+tot);
    int r=unique(b+1,b+1+tot)-b;
    for(int i=1;i<=n;++i)
    for(auto &j:g[i]) {
        j.first=lower_bound(b+1,b+r,j.first)-b;
        j.second=lower_bound(b+1,b+r,j.second)-b;
    }
    for(int i=1;i<=n;++i) {
        pair<int,int>_max={0,-1};
        for(auto &j:g[i]) 
            _max=max(_max,query(1,r,1,j.first,j.second));
        last[i]=_max.second,_max.second=i,++_max.first;
        ac=_max;
        for(auto &j:g[i])
            update(1,r,1,j.first,j.second);
    }
    for(int i=t[1].second;i;i=last[i]) vis[i]=1;
    cout<<n-t[1].first<<'\n';
    for(int i=1;i<=n;++i) if(!vis[i])
        cout<<i<<' ';
    return 0;
}