本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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 序列的子序列的长度。
数据范围：

• $1\le l\le r\le n\le 10^5$。
• $1\le q\le 10^5$。
• 保证 $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$ 减完后应是这样的：

$sum$ 是单调非递减的，$num$ 是单调非递增的。
所以，当 $sum_i<num_i$ 时，$i$ 左边的 $j$ 一定会满足：

• $sum_j<num_j$。
• $sum_j\le sum_i$。

则最终最长长度一定更短，所以我们应该向右找。
$sum_i>num_i$ 同理。

那么现在我们就想到了二分，按照上述方法模拟即可。

最终总体时间复杂度为 $\Theta(n+q\log n)$。
代码