如果你使用了奇偶性排序后RE
查看原帖
如果你使用了奇偶性排序后RE
1029038
FatFish2505楼主2024/8/29 23:57

请检查您的自定义比较函数,如果它长下面这样就会有问题(T为块长):

bool comp(Query A, Query B){
    int t1 = (A.l-1)/T, t2 = (B.l-1)/T;
    return t1==t2 ? (t1&1)^(A.r<B.r) : t1<t2;
}

这是因为,sort的自定义比较函数在两个元素“相等”时应当返回false。而以上这种写法,在 t1t1为奇数,两个询问的 l,rl, r 都相等时,会返回1^0 = true,这样sort就炸了。
正确的写法应该是这样:

bool comp(Query A, Query B){
    int t1 = (A.l-1)/T, t2 = (B.l-1)/T;
    return t1==t2 ? (t1&1 ? A.r<B.r : A.r>B.r) : t1<t2;
}

这样在两个询问的 l,rl, r 均相等时,comp必定返回false。
萌新刚学莫队,之前的几题一直用的是错误的写法,竟然都没出现过问题,终于因为这个调了1h = =

2024/8/29 23:57
加载中...