莫队
并不打算写莫队的博客,这里就只提一个容易错的点(调了我半天)
作为一个蒟蒻,之前的莫队我一直这么写的:
然而对于一些奇怪的题,在求贡献的时候l和r并不是独立的,出现了r>l的情况就会炸掉,造成莫名RE的情况,因此其实莫队这么写更好:
1、2和3、4调换一下顺序也行,总之就是不要让r>l的情况出现就对了。
这道题就是一道典型的例子:洛谷 P3246【[HNOI2016]序列】
作为一个蒟蒻,之前的莫队我一直这么写的:
while (l < s[i].l)
del(l++);
while (l > s[i].l)
add(--l);
while (r < s[i].r)
add(++r);
while (r > s[i].r)
del(r--);
然而对于一些奇怪的题,在求贡献的时候l和r并不是独立的,出现了r>l的情况就会炸掉,造成莫名RE的情况,因此其实莫队这么写更好:
while (l > s[i].l)
add(--l);
while (r < s[i].r)
add(++r);
while (r > s[i].r)
del(r--);
while (l < s[i].l)
del(l++);
1、2和3、4调换一下顺序也行,总之就是不要让r>l的情况出现就对了。
这道题就是一道典型的例子:洛谷 P3246【[HNOI2016]序列】
评论
发表评论