Codeforces Round #737 (Div. 2) D. Ezzat and Grid T2 D1

思路：

将2m个点离散化处理后，从第1行依次往下处理。处理每一行时，线段树维护上一行每个点可以更新的最大值，遍历这一行每个区间，更新最大值。

#include<bits/stdc++.h>
#define ll long long 
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((t[p].l+t[p].r)>>1) 
#define pb push_back
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void Prin(int x){
    //__int128x
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        Prin(x / 10);
    putchar(x % 10 + '0');
}

const int qs=6e5+7;
struct Tree{
	int l,r,val,add,Max;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define val(x) t[x].val
	#define add(x) t[x].add
	#define Max(x) t[x].Max
}t[qs<<2];

void build(int p,int l,int r){
	l(p)=l,r(p)=r;
	add(p)=0;
	Max(p)=0;
	val(p)=0; 
	if(l==r) {
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
}

void down(int p){
	if(add(p)==0) return;
	val(ls)=val(p);
	val(rs)=val(p);
	Max(ls)=Max(p);
	Max(rs)=Max(p);
	add(ls)=add(p);
	add(rs)=add(p);
	add(p)=0;
}

void update(int p,int l,int r,int ma,int pe){
//	cout<<"p="<<p<<" l="<<l(p)<<" r="<<r(p)<<" k="<<k<<"\n";
	if(l<=l(p)&&r>=r(p)){
		Max(p)=ma;
		val(p)=pe;
		add(p)=1;
		return;
	}
	down(p);
	if(l<=mid) update(ls,l,r,ma,pe);
	if(r>mid) update(rs,l,r,ma,pe);
	if(Max(ls)>Max(rs)) val(p)=val(ls);
	else val(p)=val(rs);
	Max(p)=max(Max(ls),Max(rs));
}

Tree ask(int p,int l,int r){
	if(l<=l(p)&&r>=r(p)){
	//	cout<<"p=="<<p<<" l=="<<l<<" r=="<<r<<" max="<<Max(p)<<" val="<<val(p)<<"\n";
		return t[p];
	}
	down(p);
	Tree te;
	Tree ml,mr; ml.Max=mr.Max=-1;
	if(l<=mid) ml=ask(ls,l,r);
	if(r>mid) mr=ask(rs,l,r);
	if(ml.Max>mr.Max) te=ml;
	else te=mr;
	return te;
}

int n,m,b[qs],pre[qs],u[qs];
vector<pii> v[qs];
//vector<pii>::iterator it;
int main(){
	n=read(),m=read();
	int h,l,r,cnt=0;
	for(int i=1;i<=m;++i){
		h=read(),l=read(),r=read();
		v[h].pb(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(int j=0;j<v[i].size();++j){
			pii &it=v[i][j];
			it.fi=lower_bound(b+1,b+1+cnt,it.fi)-b;
			it.se=lower_bound(b+1,b+1+cnt,it.se)-b;
			
		}
	}
	build(1,1,cnt);
	int ans=0,ns=0;
	for(int i=1;i<=n;++i){
		int mx=-1;
		for(int j=0;j<v[i].size();++j){
			pii it=v[i][j];
			Tree te=ask(1,it.fi,it.se);
			//cout<<"I="<<i<<" fi="<<it.fi<<"  se="<<it.se<<"\n";
			if(te.Max>mx) mx=te.Max,pre[i]=te.val;
		//	cout<<"max="<<te.Max<<" val="<<te.val<<"\n";
		}
		if(mx+1>ans) ans=mx+1,ns=i;
		//cout<<"i="<<i<<"  ans="<<ans<<"\n";
		for(int j=0;j<v[i].size();++j){
			pii it=v[i][j];
			update(1,it.fi,it.se,mx+1,i);
		}
	}
	for(int i=ns;i;i=pre[i]){
		u[i]=1;
	//	cout<<"i="<<i<<" \n";
	}
	ans=n-ans;
	Prin(ans);
	puts("");
	for(int i=1;i<=n;++i){
		if(!u[i]) Prin(i),putchar(' ');
	}
	return 0;
}