警示后人：如果你 WA*2

一句话概括：快速排序是不稳定排序。

如果你的 cdq 是这么写的：

CPP

void cdq(int l,int r){
	if(l == r){
		a[l].ans += a[l].a;
		return;
	}
	int mid = (l + r) >> 1;
	cdq(l,mid);
	// ...
	sort(a + l,a + r + 1,cmp);
	cdq(mid + 1,r);
}

而且你的 cmp 函数是这么写的：

CPP

bool cmp(node a,node b){
	if(a.y != b.y)return a.y < b.y;
	return a.t < b.t;
}

这样就有可能会寄掉。因为快速排序的不稳定性，我们有可能会把一个原本在 mid 后面的 a 放到 mid 前面，从而漏更新一些 DP 值。

解决方法有两个：

把 sort 换成 stable_sort。
把 cmp 函数换成下面这样：

CPP

bool cmp(node a,node b){
	if(a.y != b.y)return a.y < b.y;
	if(a.t != b.t)return a.t < b.t;
	return a.x < b.x;
}

警示后人：如果你 WA*2

讨论操作

回复

相关推荐

警示后人：如果你 WA*2