CF240F.TorCoder

有一个叫做 Leo 的男孩从不缺席任何 TorCoder 比赛。在上一场编号为 100666 的 TorCoder 比赛中，Leo 遇到了如下问题。他得到了一个由 $n$ 个小写英文字母组成的字符串 $s$，以及 $m$ 个询问。每个询问由一对整数 $l_{i}, r_{i}$ $(1 \leq l_{i} \leq r_{i} \leq n)$ 描述。

我们将字符串中的字母从左到右编号为 1 到 $n$，即 $s = s_{1}s_{2}\ldots s_{n}$。

对于每个询问，他必须交换字符串 $s$ 中下标从 $l_{i}$ 到 $r_{i}$（包括两端）的字母，使得子串 $(l_{i}, r_{i})$ 变成回文。如果有多种字母排列能达到这个目的，你应选择使子串 $(l_{i}, r_{i})$ 字典序最小的方案。如果不存在这样的排列，则忽略本次询问（即字符串 $s$ 保持不变）。

众所周知，在 TorCoder 比赛中，输入行数和数组大小从不会超过 60，因此 Leo 轻松解决了这个问题。你的任务是在数据规模更大的情况下完成这个问题。给定字符串 $s$ 和 $m$ 个操作，请输出全部 $m$ 次操作后所得的字符串。

从文件 input.txt 中读入数据。

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 10^{5})$——表示字符串长度和询问个数。

第二行包含长度为 $n$ 的小写英文字母字符串 $s$。

接下来的 $m$ 行中，每行包含两个整数 $l_{i}, r_{i}$（$1 \leq l_{i} \leq r_{i} \leq n$），表示一个询问。

输出到文件 output.txt 中。

一行输出经过 $m$ 次操作之后得到的字符串。按输入顺序处理所有操作。

一个长度为 $n$ 的字符串 $s=s_{1}s_{2}\ldots s_{n}$ 的子串 $(l_{i}, r_{i})\ (1\le l_{i}\le r_{i}\le n)$ 是序列 $s_{li}s_{li+1}\ldots s_{ri}$。

如果一个字符串从左到右和从右到左读都相同，则称其为回文字符串。

长度为 $p$ 的字符串 $x_{1}x_{2}\ldots x_{p}$ 的字典序小于长度为 $q$ 的字符串 $y_{1}y_{2}\ldots y_{q}$，当且仅当：
要么 $p < q$ 且 $x_{1}=y_{1},x_{2}=y_{2},\ldots ,x_{p}=y_{p}$，
要么存在某个数 $r\ (r<p,r<q)$，使得 $x_{1}=y_{1},x_{2}=y_{2},\ldots ,x_{r}=y_{r}$ 且 $x_{r+1}<y_{r+1}$。

由 ChatGPT 5 翻译