P6254 [ICPC 2019 WF] Circular DNA

你在一个研究 DNA 的生物信息学研究小组实习。单链 DNA 由许多基因组成，这些基因分为不同的类别，称为基因类型。基因类型由特定的核苷酸序列分隔，称为基因标记。每个基因类型 $i$ 有一个唯一的起始标记 $\texttt s_i$ 和一个唯一的结束标记 $\texttt e_i$。经过许多繁琐的工作（如细菌培养、细胞提取、蛋白质工程等），你的研究小组可以将 DNA 转换为仅由基因标记组成的形式，去除标记之间的所有遗传物质。 你的研究小组提出了一个有趣的假设，即基因的解释取决于某些基因类型的标记是否形成了正确的嵌套结构。要确定基因类型 $i$ 的标记在给定的标记序列 $w$ 中是否形成了正确的嵌套结构，需要考虑 $w$ 的子序列，其中只包含基因类型 $i$ 的标记（$\texttt s_i$ 和 $\texttt e_i$），不遗漏任何一个。以下（且仅以下）被认为是正确的嵌套结构： - $\texttt s_i \texttt e_i$ - $\texttt s_i N \texttt e_i$，其中 $N$ 是一个正确的嵌套结构 - $AB$，其中 $A$ 和 $B$ 是正确的嵌套结构 鉴于你的计算背景，你被分配去研究这个性质，但还有一个进一步的复杂性。你的小组正在研究一种称为环状 DNA 的特定类型的 DNA，这种 DNA 形成一个闭合的环。为了研究环状 DNA 中的嵌套，有必要在某个位置切开环，这会产生一个唯一的标记序列（读取方向由分子性质固定）。基因类型 $i$ 是否形成正确的嵌套现在也取决于环状 DNA 的切割位置。你的任务是找到最大化形成正确嵌套结构的基因类型数量的切割位置。图 D.1 显示了对应于样例输入 1 的一个例子。所示的切割导致基因类型 1 的标记正确嵌套。

输入的第一行包含一个整数 $n$ ($1 \leq n \leq 10^6$)，表示 DNA 的长度。下一行包含 DNA 序列，即 $n$ 个标记。每个标记是一个字符 $c$ 后跟一个整数 $i$，其中 $c \in \{\texttt s, \texttt e\}$ 指定它是起始还是结束标记，$i$ ($1 \leq i \leq 10^6$) 是标记的基因类型。给定的 DNA 序列是通过在任意位置切割环状 DNA 获得的。

输出一行包含两个整数 $p$ 和 $m$，其中 $p$ 是最大化形成正确嵌套结构的不同基因类型数量的切割位置，$m$ 是这个最大基因类型数量。DNA 在第 $p$ 个输入标记之前被切割（例如，图 D.1 所示的切割有 $p = 3$）。如果有多个切割位置产生相同的最大值 $m$，则输出最小的 $p$。

来源：ICPC 2019 世界总决赛。 题面翻译由 ChatGPT-4o 提供。