如果你写莫队移动指针的时候会出现某一时刻的指针 L>R,那么你可能会出错,因为你的桶中会出现 cnt<0 的情况。
因为我的 add 是这么写的,我默认 cnt 数组始终 ≥0,但是事实并非如此。
void add(int x){
cnt[x]++;
in[x+N]=mus[N-x]=1;
}
改正方法
方法1:
避免移动指针时 L>R,先调用 add,再调用 del 即可。
while(l<L){
L--;add(b[L]);
}
while(R<r){
R++;add(b[R]);
}
while(L<l){
del(b[L]);L++;
}
while(r<R){
del(b[R]);R--;
}
方法2:
在 add 时增加判断:
void add(int x){
cnt[x]++;
if(cnt[x]>0) in[x+N]=mus[N-x]=1;
}
强烈建议始终采用第一种写法,避免产生 L>R 的不符合现实的情形。