警示后人
查看原帖
警示后人
1030875
born_to_sun楼主2024/8/16 09:05

如果你写莫队移动指针的时候会出现某一时刻的指针 L>RL>R,那么你可能会出错,因为你的桶中会出现 cnt<0cnt<0 的情况。

因为我的 addadd 是这么写的,我默认 cntcnt 数组始终 ≥0\geq 0,但是事实并非如此。

void add(int x){
	cnt[x]++;
	in[x+N]=mus[N-x]=1;
}

改正方法

方法1:

避免移动指针时 L>RL>R,先调用 addadd,再调用 deldel 即可。

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:

在 addadd 时增加判断:

void add(int x){
	cnt[x]++;
	if(cnt[x]>0) in[x+N]=mus[N-x]=1;
}

强烈建议始终采用第一种写法,避免产生 L>RL>R 的不符合现实的情形。

2024/8/16 09:05
加载中...