Oql's Blog

发表于 分类于

题意

给定 $N$ 个仅有 小写字母组成的字符串 $a_ i$,每个字符串都有一个权值 $v_i$ ,有 $M$ 次操作，操作分三种：

  • Cv x v’:把第x个字符串的权值修改为v’

  • Cs x a’:把第x个字符串修改成a’

  • Q:求出当前的最大权字符串集合，使得这个集合中的字符串经过重新排列后满足除最后一个字符串外，前一个字符串是后一个的前缀(两个字符串相同也是前缀关系，也可以一个字符串都不选)

前50%的数据可以接受离线算法，后50%的数据要求在线算法。

$N\le 50000,M\le 10^5$ ，字符串总长 $\le 10^6$。

阅读全文 »