AtCoder Beginner Contest 381-E
Problem
一个长度为奇数、最中间的那个字符是 /、左边所有字符都是都是 1、右边所有字符都是 2 的字符串被称为11/22 字符串。
更加严谨的定义：
当一个字符串 \(T\) 满足以下所有条件时，它被称为11/22 字符串：
- \(|T|\) 是奇数。这里， \(|T|\) 表示 \(T\) 的长度。
- 从第 \(1\) 到第\((\frac{|T|+1}{2} - 1)\) 个字符都是
1。- 第 \((\frac{|T|+1}{2})\) 个字符是
/。- 从第 \((\frac{|T|+1}{2} + 1)\) 到第 \(|T|\) 的字符都是
2。
例如，11/22、111/222和/是 11/22 字符串，但1122、1/222、11/222、22/11和/2/2/211则不是。
给定由1、2和/组成的字符串 \(S\) ，\(|S|=N\)。有 \(Q\) 次询问：给定 \(L\) 和 \(R\)，设 \(T\) 是 \(S\) 的从第 \(L\) 个字符到第 \(R\) 个字符组成的子串。请找出 \(T\) 的最长子序列使得该子序列是一个 11/22 字符串。如果不存在这样的子序列，则打印 "0"。
Constraints
- \(1 \leq N \leq 10^5\)
- \(1 \leq Q \leq 10^5\)
- \(S\) is a string of length \(N\) consisting of
1,2, and/. - \(1 \leq L \leq R \leq N\)
- \(N\), \(Q\), \(L\), and \(R\) are integers.