YZOJ P3389 [FOI 2018 四校联训 Round 3]消息密匙

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\) 进制分解,一个个连通块按编号从小到大分配即可。

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注