P5685 [JSOI2013] 快乐的 JYY：区间 DP 与分块

题面简述

给定一个长度为 $n$ 的字符串，每次询问给出一个区间 $[l, r]$ ，问把区间内的字符重排后，能得到多少个回文串（允许为空）。

先说结论：这道题我第一次做是错的。错在把「区间修改」当成了「点修改」，多算了一个 log。

朴素做法

设 $f[l][r]$ 表示区间 $[l,r]$ 重排后能拼出的最长回文长度，那么答案就是：

f[l][r] = \begin{cases} 1 & l = r \\ 2 \cdot \sum_{c} \left\lfloor \frac{cnt_c(l,r)}{2} \right\rfloor + [\exists c : cnt_c(l,r) \text{ 为奇数}] & l < r \end{cases}

这个转移是对的，问题是复杂度。 $O(n^2)$ 个状态，每个状态要遍历 26 个字符， $O(26 n^2)$ 直接炸。

关键观察

我们不需要真的维护所有区间的答案。注意到：

结论 1：字符集大小固定为 26，那么「区间内每种字符出现次数的奇偶性」只有 $2^{26}$ 种可能，太多了。但我们只需要「奇数个字符的数量」这一个标量。

结论 2：设 $odd(l,r)$ 为区间内出现奇数次的字符种数，则

f[l][r] = (r - l + 1) - odd(l,r) + [odd(l,r) > 0]

即「配对数 $\times 2$ + 至多一个落单的字符」。

于是问题转化成了：区间内有多少种字符出现了奇数次。

分块做法

对位置分块，块长 $B = \sqrt{n}$ 。

维护每个块内 26 个字符的前缀计数（块内相对位置）。
询问 $[l,r]$ 时，暴力处理两端的散块（ $O(B)$ ），中间完整块用前缀计数向量相减，得到各字符总次数。
得到总次数后，统计奇数个数需要 $O(26)$ 。

单次询问 $O(B + 26 \cdot n/B)$ ，取 $B = \sqrt{n}$ ，复杂度 $O(\sqrt n)$ 。

但题目还有修改操作。如果每次修改都重建块前缀，需要 $O(B \cdot 26)$ 。

我踩的坑

第一次提交是 $O(n \sqrt n \log n)$ 的，原因是：

我用 std::map 维护块内每个字符的出现位置集合；
修改时先删除再插入，每次 $O(\log B)$ ；
查询时对每个字符用 lower_bound 算它在区间内的出现次数，26 次 $\log$ 。

其实根本不需要位置集合。只需要计数。把 map<int,int> 换成 array<int,26>，修改直接 ` $O(1)$ 加减$，查询用前缀计数差分，复杂度降一个 log。

// 块内字符计数的前缀和
struct Block {
    vector<array<int,26>> pre;  // pre[i][c] = 前 i 个字符中 c 的出现次数
};

int queryOdd(int l, int r) {
    int cnt[26] = {0};

    // 左散块
    if (blockOf[l] == blockOf[r]) {
        for (int i = l; i <= r; i++) cnt[s[i]]++;
    } else {
        int lb = blockOf[l], rb = blockOf[r];
        for (int i = l; i <= R[lb]; i++) cnt[s[i]]++;
        for (int i = L[rb]; i <= r; i++) cnt[s[i]]++;
        for (int b = lb + 1; b < rb; b++) {
            for (int c = 0; c < 26; c++)
                cnt[c] += Block[b].pre[blockLen] - Block[b].pre[0];
        }
    }

    int odd = 0;
    for (int c = 0; c < 26; c++) odd += (cnt[c] & 1);
    return odd;
}

修改时只需更新受影响块的 pre 数组（ $O(B \cdot 26)$ ），以及散块。

复杂度小结

操作	复杂度
单点修改	$O(B \cdot 26)$
区间询问	$O(B + 26 \cdot n/B)$
总计	$O(n \sqrt n)$

一些别的话题

其实这题还有另一个思路：用 莫队 + 哈希 维护奇偶性的位集，cnt 用 uint32_t 存 26 个 bit，异或即可。询问莫队复杂度 $O(n \sqrt n)$ ，但不支持修改。

如果题目允许离线（没有强制在线），莫队版本更短也更稳。我提交时没注意「强制在线」四个字，被卡了两次。

教训：读题的时候把「强制在线」这类词圈出来，它直接决定算法选型。