前言

下文中使用 std::tuple<int,int,int> 来存储一个询问，存储的三个元素分别表示询问左端点、询问右端点、询问编号。变量 sq 为块长。

哪里错了？

来看如下的一段对若干个询问进行奇偶性排序的代码：

sort(Q.begin(),Q.end(),[&](tpi x,tpi y)->bool{
  if(get<0>(x)/sq!=get<0>(y)/sq)return get<0>(x)<get<0>(y);
  return (get<1>(x)<get<1>(y))^get<0>(x)/sq&1;
});

这份代码在评测中获得了 RE $68$ 分的好成绩，上面是出错的地方。

解释一下，(get<1>(x)<get<1>(y))^get<0>(x)/sq&1，表示根据块的编号奇偶性来决定右端点的排序方式（从大到小 / 从小到大），优先级并没有问题。

你可以先自行思考一下错在哪里。

原因 & 正确写法

std::sort 有一个特性，对于两个元素 $x,y$，令传入的比较函数为 $\mathrm{cmp}$，如果 $\operatorname{cmp}(x,y)=\operatorname{cmp}(y,x)=\mathrm{true}$，程序就会报错。

而对于上面的代码，只需放两个相同的询问 $[l,r]$，它就会 RE。

以下是奇偶性排序的正确写法：

sort(Q.begin(),Q.end(),[&](tpi x,tpi y){
  if(get<0>(x)/sq!=get<0>(y)/sq)return get<0>(x)<get<0>(y);
  return get<0>(x)/sq&1?get<1>(x)<get<1>(y):get<1>(x)>get<1>(y);
});