CF217E Alien DNA

Bajtocy 教授正在进行关于外星 DNA 的实验。他发现这种 DNA 会发生重复突变 —— 每次突变的过程都是一样的：DNA 的某一连续子序列被激活，自我复制，然后这个复制品经过扰乱处理后插入到原子序列的后面。扰乱处理的方式是：先将该子序列中所有偶数位置的元素按顺序连接，然后再将所有奇数位置的元素按顺序连接并接在后面。也就是说，如果被激活的子序列有 11 个元素、表示为 $s_1 s_2 \ldots s_{11}$，其扰乱后的副本即为 $s_2 s_4 s_6 s_8 s_{10} s_1 s_3 s_5 s_7 s_9 s_{11}$。 例如，原始序列为 "ACTGG"，如果在区间 $[2,4]$（即被激活的子序列为 "CTG"）上发生突变，则突变后的 DNA 序列为："ACTGTCGG"。其中扰乱处理后的副本已用黑体标出。 Bajtocy 教授已经记录下了最初的 DNA 序列以及其上依次发生的所有突变，现在他希望你帮他恢复所有突变发生后 DNA 序列的前 $k$ 个元素。

第一行为原始的 DNA 序列，只包含字母 "A"、"C"、"T"、"G"，长度不超过 $3 \times 10^6$。 第二行为一个整数 $k$，表示你需要输出突变后 DNA 序列的前 $k$ 个字符（$1 \leq k \leq 3\times 10^6$）。 第三行为一个整数 $n$，表示突变的次数（$0 \leq n \leq 5000$）。接下来的 $n$ 行每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq 10^9$），表示在 DNA 序列中从第 $l_i$ 个元素到第 $r_i$ 个元素（包含首尾，闭区间）这个子序列被激活并发生了如上描述的突变。 保证输入数据合法，即不会有突变作用在不存在的 DNA 元素上，并且所有突变结束后 DNA 序列长度至少为 $k$。 DNA 元素下标从 1 开始。$[l, r]$ 表示从第 $l$ 位到第 $r$ 位的连续子序列，共有 $r-l+1$ 个元素。

输出突变后 DNA 序列的前 $k$ 个字符，全部输出在一行。

例如第二个样例，第一次突变后序列变为 "ACCAGTACGT"。第二次突变后变为 "ACCAGTACCGACATCGT"。 由 ChatGPT 5 翻译