你好！非常棒，看来你已经掌握了前面的内容。接下来我们进入高中生物必修二《遗传与进化》的核心章节——基因的表达。

这道题的背景涉及“中心法则”中的转录和剪接过程，考察的是字符串处理、标记法（Flagging）以及时间复杂度优化的意识。难度定位 GESP 5级（约等于 CSP-J 普及组 T2）。

题目：成熟的信使（The Mature Messenger）

【背景知识讲解】

在生物体内，基因的表达主要分为两步：

1. 转录（Transcription）：以DNA为模板合成前体mRNA（Pre-mRNA）。在这个过程中，DNA中的碱基 T（胸腺嘧啶） 会变为 RNA 中的 U（尿嘧啶），其余（A, C, G）保持不变（注：为了简化题目，这里暂不考虑碱基互补配对，只考虑T变U的替换）。
2. 剪接（Splicing）：真核生物的基因是“断裂”的。
   • 内含子（Intron）：基因中不编码蛋白质的片段，需要被剪切掉。
   • 外显子（Exon）：编码蛋白质的片段，需要被保留并拼接在一起。

剪接过程就是把“内含子”切掉，把“外显子”连起来，形成成熟的mRNA。

【题目描述】

你是一名生物信息学家，刚刚测序得到了一段长度为 $N$ 的前体mRNA序列 $S$（此时还包含内含子，且尚未将 T 替换为 U）。 同时，实验室给出了 $K$ 个内含子在序列中的位置区间。 请你完成以下任务：

1. 将序列中所有的字符 'T' 替换为 'U'。
2. 根据给出的 $K$ 个区间，删除这些位置上的碱基。
3. 将剩下的片段按原顺序拼接，输出最终的成熟mRNA序列。

注意：

• 给出的 $K$ 个内含子区间保证互不重叠，且都在序列范围内。
• 区间是闭区间 $[L, R]$，位置下标从 $1$ 开始计数。

【输入格式】

第一行包含两个整数 $N$ 和 $K$，分别表示序列总长度和内含子的数量。 第二行包含一个长度为 $N$ 的字符串 $S$，仅包含 'A', 'T', 'C', 'G'。 接下来 $K$ 行，每行包含两个整数 $L_i, R_i$，表示第 $i$ 个内含子的起始和结束位置（1-based）。

【输出格式】

输出一行字符串，表示处理后的成熟mRNA序列。

【样例数据】

输入：

15 2
ATGCGTATCCGTACT
2 4
10 12

输出：

AGUAUCACU

样例解释： 原始序列：A T G C G T A T C C G T A C T (长度15) 下标：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1. 标记内含子区间（需要删除的部分）：
   • 区间 [2, 4] 对应 T G C (下标2,3,4)
   • 区间 [10, 12] 对应 C G T (下标10,11,12)
2. 保留外显子部分：
   • 下标 1: A
   • 下标 5-9: G T A T C
   • 下标 13-15: A C T
3. 转录（T替换为U）并拼接：
   • 下标 1: A
   • 下标 5-9: G U A U C (T变U)
   • 下标 13-15: A C U (T变U)
4. 最终结果：
   • A + GUAUC + ACU = AGUAUCACU

【数据范围】

• 对于 100% 的数据：$1 \le N \le 1,000,000$，$0 \le K \le 100,000$。
• $1 \le L_i \le R_i \le N$。
• 保证所有区间互不重叠。

一、 思路提示

1. 直接模拟的陷阱：
   • 如果你使用字符串的 erase 函数（例如 s.erase(pos, len)），每删除一次，后面的字符都会向前移动。
   • 一旦 $N$ 很大，且 $K$ 很大，反复移动字符的时间复杂度会达到 $O(N \times K)$，这在 $N=10^6$ 时会超时。
2. 换个角度：
   • 与其“真的把字符删掉并移动数组”，不如“挑选需要的字符”。
   • 或者，我们可以给每个位置打上一个“标签”：这个位置是“保留”还是“丢弃”？
3. 标记法（Flagging）：
   • 开一个布尔数组 bool is_removed[N+1]，初始化为 false。
   • 读入一个区间 $[L, R]$，就把数组中下标 $L$ 到 $R$ 的位置都标记为 true。
   • 最后遍历整个字符串，如果 is_removed[i] 是 false，就输出该字符（记得把 T 变 U）；如果是 true，就跳过。

二、 预备知识点总结

1. 布尔数组/标记数组：用于以 $O(1)$ 的时间记录某个位置的状态。
2. 字符串遍历：线性扫描。
3. 时间复杂度意识：理解为什么字符串频繁删除操作是昂贵的，学会用空间换时间（开一个数组标记，换取不进行移动操作）。

三、 启发式教学：草稿纸上的推理过程

教练：“大家想象一下，这串DNA就像是一条长长的胶卷底片。”

1. 画图：
   • 我们在纸上画 10 个格子代表序列。
   • 1 2 3 4 5 6 7 8 9 10
2. 操作区间：
   • 题目说要剪掉区间 [2, 4]。
   • 能不能拿剪刀直接剪？在电脑里，“剪”意味着把后面的 5 6 7... 全部往前挪，填补空缺。这太累了（太慢了）。
3. 涂黑策略：
   • 不如我们拿一支黑色马克笔。
   • 看到区间 [2, 4]，就把格子 2, 3, 4 涂黑。
   • 看到下一个区间，继续涂黑。
4. 最后扫描：
   • 现在我们从头走到尾。
   • 格子1：没涂黑 $\to$ 抄下来（记得 T 变 U）。
   • 格子2：涂黑了 $\to$ 跳过。
   • 格子3：涂黑了 $\to$ 跳过。
   • ...
   • 这样是不是只需要走一遍（$O(N)$）就搞定了？

教练：“还有一个小细节，输入的区间可能是乱序的吗？如果是乱序的，用涂黑法受影响吗？” 学生：“不受影响！只要涂黑了就行，先涂哪一块都一样。” 教练：“非常好。这就是标记法的强大之处。”

四、 读题关键词总结

1. “删除” / “剪接” $\rightarrow$ 涉及子串移除。
2. $N=10^6$ $\rightarrow$ 禁止使用 $O(N^2)$ 的算法（如频繁的 string::erase 或 vector::erase）。必须 $O(N)$ 解决。
3. “区间互不重叠” $\rightarrow$ 降低了难度，不需要处理区间合并，直接标记即可。
4. “T 替换为 U” $\rightarrow$ 输出时的简单字符转换逻辑。