有关莫队与考试防爆

学术版

您好,为避免发生还没插入某元素就先删除它的情况发生,请先拓展区间,再收缩区间。当然,对于元素求和的特殊情况,先收缩再拓展也是可行的。
by only_a_speaker @ 2023-10-19 15:27:43


第一个只要先扩张区间后收缩区间就没事,主要是保证过程中左端点不会到右端点右边。 第二个我也很想知道。
by fangzichang @ 2023-10-19 15:28:46


@[yyz1005](/user/220824) 1. 似乎有多种写法(我记得 oi-wiki 上有详细分析?),我一般这么写: ```cpp 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:28:55


其实第一问还是要就题论题;比如 P5071 就不能用我上面的写法,否则在指针移动过程中统计因子个数的 cnt 数组会出现负数。
by lsj2009 @ 2023-10-19 15:31:06


@[lsj2009](/user/468657) 您这种是不是错的啊/yiw 这应该算 oi-wiki 里的 `l++,l--,r++,r--` 类型。 <https://oi-wiki.org/misc/mo-algo/#%E8%BF%87%E7%A8%8B>
by 沉石鱼惊旋 @ 2023-10-19 15:36:39


@[沉石鱼惊旋](/user/516346) /jk,但是我这么写从没挂过欸,
by lsj2009 @ 2023-10-19 15:37:25


哦哦,我这种写法在刚才说的 P5071 就会挂,所以还是说就题论题吧。
by lsj2009 @ 2023-10-19 15:39:11


所以说只要不出现一个点在加入之前删除就可以了吗
by yyz1005 @ 2023-10-19 15:45:14


先扩张再收缩。
by cmaths @ 2023-10-19 15:46:31


2.对拍、测极端数据
by cmaths @ 2023-10-19 15:49:40


| 下一页