有关莫队与考试防爆

yyz1005 @ 2023-10-19 15:22:59

by only_a_speaker @ 2023-10-19 15:27:43

您好，为避免发生还没插入某元素就先删除它的情况发生，请先拓展区间，再收缩区间。当然，对于元素求和的特殊情况，先收缩再拓展也是可行的。

by fangzichang @ 2023-10-19 15:28:46

第一个只要先扩张区间后收缩区间就没事，主要是保证过程中左端点不会到右端点右边。
第二个我也很想知道。

by lsj2009 @ 2023-10-19 15:28:55

@yyz1005

1. 似乎有多种写法（我记得 oi-wiki 上有详细分析？），我一般这么写：

rep(i,1,q) {
    while(l<que[i].l)
        del(a[l++]);
    while(l>que[i].l)
        add(a[--l]);
   while(r<que[i].r)
        add(a[++r]);
    while(r>que[i].r)
        del(a[r--]);
    ans[que[i].id]=calc(l,r);
}

2. 如果你开了 warning，我觉得不会有这种问题。

by lsj2009 @ 2023-10-19 15:31:06

其实第一问还是要就题论题；比如 P5071 就不能用我上面的写法，否则在指针移动过程中统计因子个数的 cnt 数组会出现负数。

by 沉石鱼惊旋 @ 2023-10-19 15:36:39

@lsj2009 您这种是不是错的啊/yiw

这应该算 oi-wiki 里的 l++,l--,r++,r-- 类型。

https://oi-wiki.org/misc/mo-algo/#%E8%BF%87%E7%A8%8B

by lsj2009 @ 2023-10-19 15:37:25

@沉石鱼惊旋 /jk，但是我这么写从没挂过欸，

by lsj2009 @ 2023-10-19 15:39:11

哦哦，我这种写法在刚才说的 P5071 就会挂，所以还是说就题论题吧。

by yyz1005 @ 2023-10-19 15:45:14

所以说只要不出现一个点在加入之前删除就可以了吗

by cmaths @ 2023-10-19 15:46:31

先扩张再收缩。

by cmaths @ 2023-10-19 15:49:40

2.对拍、测极端数据