多查询场景下字符串区间重排为最小回文的求解问题

核心思路 #

采用支持区间字符计数查询、区间批量赋值的线段树处理所有查询，单次查询复杂度为常数倍O(logn)，可满足1e5数据量的性能要求。

具体实现步骤 #

• 第一步：构建线段树
  每个线段树节点存储两个信息：
  • 长度为26的计数数组cnt，cnt[i]表示当前区间内第i个小写字母的出现次数
  • 懒标记lazy，取值为-1_{25，-1表示无懒标记，0}25表示当前区间所有字符已被统一赋值为对应小写字母
    线段树默认支持两个操作：区间字符计数查询、区间批量赋值为指定字符，两个操作的时间复杂度均为O(logn)
• 第二步：逐个处理每次查询
  1. 取当前查询的区间[L, R]，调用线段树的区间查询接口，拿到该区间26个字母的出现次数
  2. 回文合法性判断：统计出现次数为奇数的字符数量odd_cnt，若区间长度为偶数且odd_cnt != 0，或区间长度为奇数且odd_cnt != 1，直接跳过本次查询
  3. 构造最小字典序回文的分段结构：
     • 计算半长half = (R - L + 1) // 2
     • 按a到z的顺序遍历26个字母，每个字母取cnt[i] // 2个作为前半段的字符，按从小到大顺序排列可保证前半段字典序最小
     • 若区间长度为奇数，记录唯一的出现奇数次的字符作为中间字符
     • 后半段为前半段的逆序，保证整体为回文
  4. 批量执行区间赋值：
     • 前半段从L开始，按连续相同字符拆分为最多26个连续区间，逐个调用线段树的区间赋值接口赋值
     • 若存在中间字符，对中间位置单独赋值
     • 后半段从R开始，按逆序后的连续相同字符拆分为最多26个连续区间，逐个调用区间赋值接口赋值
• 第三步：所有查询处理完成后，遍历线段树或者执行一次全区间查询，按位置输出每个字符即可得到最终字符串

实现时需注意线段树的下标要和题目给出的区间下标保持一致，建议采用1-based的下标实现，避免偏移转换出错。

复杂度分析 #

• 单次查询中，区间计数查询复杂度为O(26logn)，批量赋值最多执行2*26+1次区间赋值操作，每次复杂度O(logn)，总单次查询复杂度为O(logn)
• 整体复杂度为O(n + Q*logn)，可轻松处理1e5级别的数据量

内容的提问来源于stack exchange，提问作者Arijeet Mohanty