首先能够想到枚举所有的 /，对于每个 / 计算以它为中间字符时能够产生的最大答案。对于当前询问的区间 \((l,r)\)，设 \(pos\) 表示当前这个 / 的位置。如果令 \(s1\) 表示区间 \([l,pos]\) 里 1 的数量，\(s2\) 表示区间 \([pos,r]\) 里 2 的数量，那么此时的答案显然就是 \(\min(s1,s2)+1\)。其中 \(s1\) 和 \(s2\) 可以用前缀和维护。
但是直接枚举肯定是不行的。我们不妨感性理解一下，作为断点字符的 / 一定要尽可能靠近中间，于是不难想到二分。
具体的，我们预处理所有 / 的位置，每次先二分找到所有在当前询问范围内的 / 位置区间，设这个区间为 \([L,R]\)。然后在这个集合内二分找到最优的 / 的位置。
在 \(check\) 的时候，我们对于当前的 \(mid\)，找到区间 \([L,mid]\) 中 1 的数量 \(sum1\)，区间 \([mid,R]\) 中 2 的数量 \(sum2\)，那么如果 \(sum1\le sum2\)，就收缩左端点，否则收缩右端点。
二分的收缩，边界等细节其实不用过多考虑。对于我来说，最后可以把最优位置所在的区间收缩到一个大概不超过 \(10\) 的范围，在这个范围里全部重新计算贡献，就可以不用考虑边界问题，足以通过本题。
标签：11,二分,22,题解,s1,pos,mid,s2,区间 From： https://www.cnblogs.com/Lydic/p/18563814