关于奇偶化排序莫队
查看原帖
关于奇偶化排序莫队
750579
LEE114514楼主2023/8/31 08:31

本人做法普通莫队 + 值域分块,以下是奇偶化排序的结果。

奇偶化排序代码:

struct Q{
	int l,r;
	bool operator<(const Q &tmp) const{
		if(id[l]==id[tmp.l]) return (r>tmp.r)^(l&1);
		return l<tmp.l;
	}
	int ind;
}q[maxn];

即使改变右端点排序的不等号方向依然超时。

然而,这是普通排序的结果。

普通排序代码:

struct Q{
	int l,r;
	bool operator<(const Q &tmp) const{
//		if(id[l]==id[tmp.l]) return (r>tmp.r)^(l&1);
		if(id[l]==id[tmp.l]) return r<tmp.r;
		return l<tmp.l;
	}
	int ind;
}q[maxn];

难道普通莫队奇偶化排序会被卡吗?普通莫队可以放心写奇偶化排序吗?

2023/8/31 08:31
加载中...