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$ 小的合法的能被填出的串。

• 样例输入

• 样例输出

• 数据规模与约定

对于 $100\%$ 的数据，保证 $n,m \leq 5 \times 10^5, k \leq 1 \times 10^{18}$ 。

 

 

 

---

 

 

 

首先把每个 $\text{‘?’}$ 变成一个 $>26$ 的数字编号，然后序列翻转使用平衡树（Treap，Splay，pb_ds等）维护。

如果原串或新串中有的字符不为 $\text{‘?’}$ ，那么就可以直接确定这一位上的字母。

如果都为 $\text{‘?’}$ 的话，就用并查集把它们并起来。

最后，一个连通块内的字母一定是相同的。

因为有字典序的限制，所以并查集并的时候注意编号小的作为根节点。

字典序 $K$ 大怎么求？把它 $26$ 进制分解，一个个连通块按编号从小到大分配即可。