[ABC381E] 11/22 Subsequence 讲解

zrl123456 · 2024-11-23 12:59:08 · 题解

[ABC381E] 11/22 Subsequence

题目考察：二分，前缀和。
题目简述：
定义 11/22 序列为由 k 个 1，1 个 / 和 k 个 2 拼接而成的字符串（k 为 非负整数）。q 次询问，每次询问求长度为 n 的字符串 s 的 l 到 r 位的最长的是 11/22 序列的子序列的长度。
数据范围：

• 保证 s 只有 1、2 和 / 组成。

  贪心的想，对于每一个 /，他前面的所有 1 （设有 sum 个）和后面的所有 2 （设有 num 个）都可以放在他的前面（后面）形成一个子序列，但 1 和 2 的数量要相等，所以最长长度为 2\min(sum,num)+1。
  前面 1 的个数和后面 2 的个数均可用前（后）缀和预处理得到（设为 sum_i 和 num_i）。
  但是我们截取 [l,r] 区间后，sum_i 要减去 sum_{l-1}，num_i 要减去 num_{r+1}，我们就无法预处理每个 / 的最长长度了。

我们发现，最后 sum 和 num 减完后应是这样的：