1 条题解
-
0
题意:
给定一个长度为 的字符串, 次询问区间能重排成回文串的子区间计数。
$1 \leq n, m \leq 6 \times 10^4, \left| \sum ^ * \right| = 26$ 。
题解:
区间重排成回文串等价于区间出现出现次数为奇数的字符的个数不超过 。
将 映射到 的一组向量基。则区间出现次数均为偶数等价于区间 之和 。有一个数出现次数为奇数等价于 和等于选取的基的一个向量(数)。
不妨取
1 << i
, 。由于向量长度比较短(26),可以直接暴力扫,
问题转化到可以简单地由普通莫队维护的信息。区间 可以很简单地差分,用两个后缀 的 来表示。
- 1
信息
- ID
- 2537
- 时间
- 3000ms
- 内存
- 159MiB
- 难度
- 6
- 标签
- 递交数
- 4
- 已通过
- 4
- 上传者