标签: 莫队

2 篇文章

LuoguP3604 美好的每一天
Description 题目链接:P3604 给定一个长度为 $n$ 的字符串(仅包含小写字母),有 $m$ 个询问区间 $[l,r]$,求区间的子区间重排能成为一个回文串的个数。 $1\leq n,m\leq 6\times 10^4$ Solution 数据范围较小,考虑莫队。 一个字符串重排能成为回文串的条件是出现次数最多有一个是奇数。 由于…
浅谈莫队
简介 莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前,莫队算法已经在 Codeforces 的高手圈里小范围流传,但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时,只分析了普通莫队算法,但是经过 OIer 和 ACMer 的集体智慧改造,莫队有了多种扩展版本。莫队算法可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩…