其中 \(g(i,j)\) 为一个布尔函数，表示第 \(i,j\) 行是否可以相邻。

这显然是一个 \(O(n^3)\) 级别的算法，我们考虑优化一下，可以用线段树。

我们假设现在考虑已经求出对于 \(j\in [1,i]\) 中的所有 \(f_j\)，我们线段树维护的是目前，区间所被覆盖的行中 \(f_i\) 值最大的那一个，这样我们在求解 \(f_{i+1}\)? 时，可以利用线段树上的信息了。

最后答案就是 \(n-\max\limits_{i=1}^n f_i\)。

求解方案的话，只要记录一下决策点即可。

时间复杂度 \(O(n\log n)\)。线段树帮助我们省去了枚举 \(j\) 和计算 \(g\) 函数的时间。

代码

注意有几处等于号一定要有，否则会错。

别问我怎么知道。

22次的提交记录告诉我的

原因的话，是因为可能因为 pushup 操作导致父节点的 \(maxx\)? 值已经正确，但是另外一个子节点无法更新到。

这话很抽象，最好在实践中理解。。。。。

//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}

const int MAXN=3e5+10; 

int n,m,len,cnt;
struct segment {
	int maxx,lazy;
}s[MAXN<<3];
struct sgm {
	int id,l,r;
}sm[MAXN];
int num[MAXN<<1],f[MAXN],g[MAXN];
bool vis[MAXN];
vector vec[MAXN];

void pushdown(int l,int r,int p) {
	if(l==r) {
		return ;
	}
	int mid=(l+r)>>1;
	if(f[s[p].lazy]>=f[s[p<<1].maxx]) {
		s[p<<1].maxx=s[p].lazy;
		s[p<<1].lazy=s[p].lazy;
	}
	if(f[s[p].lazy]>=f[s[p<<1|1].maxx]) {
		s[p<<1|1].maxx=s[p].lazy;
		s[p<<1|1].lazy=s[p].lazy;
	}
	s[p].lazy=0;
}
segment pushup(segment lft,segment rgt) {
	segment ret=s[0];
	if(f[lft.maxx]>f[rgt.maxx]) {
		ret.maxx=lft.maxx;
	}
	else {
		ret.maxx=rgt.maxx;
	}
	return ret;
}

void modify(int l,int r,int p,int x,int y,int val) {
	if(r=f[s[p].maxx]) {
            //here
			s[p].maxx=val;
			s[p].lazy=val;
		}
		return ;
	}
	
	int mid=(l+r)>>1;
	modify(l,mid,p<<1,x,y,val);
	modify(mid+1,r,p<<1|1,x,y,val);
	s[p]=pushup(s[p<<1],s[p<<1|1]);
}
segment query(int l,int r,int p,int x,int y) {
	if(r>1;
	return pushup(query(l,mid,p<<1,x,y),query(mid+1,r,p<<1|1,x,y));
}

int get(int x) {
	return lower_bound(num+1,num+len+1,x)-num;
}

signed main() {

	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		sm[i].id=read();num[++cnt]=sm[i].l=read();num[++cnt]=sm[i].r=read();
	}
	sort(num+1,num+cnt+1);
	len=unique(num+1,num+cnt+1)-num-1;
	
	for(int i=1;i<=m;i++) {
		sm[i].l=get(sm[i].l);
		sm[i].r=get(sm[i].r);
		vec[sm[i].id].push_back(sm[i]);
	}
	
	int tp=0,maxx=0;
	for(int i=1;i<=n;i++) {
		if(i==6) {
			int hhh;
			hhh++;
		}
		segment ans=s[0];
		int sz=vec[i].size();
		for(int j=0;jmaxx) {
			maxx=f[i];
			tp=i;
		}
		
		for(int j=0;j