跳转至

莫队

  • 注意能否构造数据使得块长为 \(0\)，导致除 \(0\) 错误；
  • 注意桶数组的大小，应为值域 \(V\)；
  • 注意奇偶块排序比较函数的的严格弱序；

严格弱序

sort() 使用的比较函数需要满足严格弱序，即满足以下三个性质：

  • 非自反性：cmp(a, a) -> false；
  • 反对称性：若 cmp(a, b) == true，则 cmp(b, a) = false；
  • ​传递性：若 cmp(a, b) == true，cmp(b, c) == true，则 cmp(a, c) -> true；

使用奇偶块排序时尤其需要注意这一点。比如

inline bool operator<(const Query& other) const {
    if(blo[l] ^ blo[other.l]) return blo[l] < blo[other.l];
    return (r < other.r) ^ (blo[l] & 1);
}

就不是严格弱序。因为当 r == other.r 且 blo[l] & 1 时，它不满足反对称性。因此我们应该这样写：

inline bool operator<(const Query& other) const {
    if(blo[l] ^ blo[other.l]) return blo[l] < blo[other.l];
    if(blo[l] & 1) return r < other.r;
    return r > other.r;
}