YZOJ P3389 [FOI 2018 四校联训 Round 3]消息密匙
时间限制：3000MS 内存限制：131072KB
难度：\(6.0\)
-
题目描述
已知密匙与一个长度为 \(n\) 的字符串有关，字符串中的字符都来自于字符集 \(\{\text{‘a’..}\text{‘z’}, \text{‘?’}\}\)，每个 \(\text{‘?’}\) 的位置都要被填上一个小写字母，我们定义一个填好的串是合法的当且仅当它满足如下条件：
在输入的 \(m\) 次操作后与这个串操作之前的样子相比没有改变。
一次操作是翻转这个串的第 \(l_i\) 个字符到第 \(r_i\) 个字符。
求出字典序第 \(K\) 小的合法的能被填出的串，因为密码就是它。
-
输入格式
第一行三个数 \(n,m,k\) 。
第二行一个长度为 \(n\) 的串。
接下来 \(m\) 行每行两个数 \(l_i\) 和 \(r_i\) 。
-
输出格式
一个串，表示字典序第 \(K\) 小的合法的能被填出的串。
-
样例输入
|
1 2 3 |
12 1 4 ztrs?a?isred 5 7 |
-
样例输出
|
1 |
ztrsdadisred |
-
数据规模与约定
对于 \(100\%\) 的数据，保证 \(n,m \leq 5 \times 10^5, k \leq 1 \times 10^{18}\) 。