P3604

题意 给定一个字符串 \(S\)，每次区间查询 \(l, r\) 中有多少子区间重排可以形成回文串。 Sol 莫队板子题。 首先套路地，状压 \(26\) 个字母，然后做异或前缀和。 问题变为当前区间内有多少个 \([x, y]\) 使得 \(s[y] \oplus s[x - 1]\) 有或者没有 ......

原题 非常好的一道题 起初没看数据范围，以为是类似于区间的子区间性质的问题，口胡了一个扫描线+主席树的做法，然后发现要重排 首先读题，要重排后为回文串 然后发现数据范围很小，考虑根号算法。发现对于一个回文串，区间里的数要么都出现两次，要么有一个出现一次。这很类似于异或操作 于是我们考虑先对数状压一下 ......

[传送门](https://www.luogu.com.cn/problem/P3604) # 好题！ 首先说这道题的时间复杂度：$O(26n\sqrt n)$。因为转移是的常数是 $O(26)$ 并非 $O(1)$，这启示我们，**看数据范围，不要被O(1)给限制了，O(1)是一般情况，有些题不一 ......