6690: BZOJ2690：字符串游戏

给定N个仅有a~z组成的字符串ai,每个字符串都有一个权值vi,有M次操作，操作分三种： Cv x v':把第x个字符串的权值修改为v' Cs x a':把第x个字符串修改成a' Q:求出当前的最大权字符串集合，使得这个集合中的字符串经过重新排列后满足除最后一个字符串外，前一个字符 串是后一个的前缀(两个字符串相同也是前缀关系，也可以一个字符串都不选) 前50%的数据可以接受离线算法，后50%的数据要求在线算法。

输入格式

输入的第一行包含一个正整数Test表示当前的数据类型。 输入的第二行包含两个正整数N,M表示字符串数和操作数。 以下N行，每行一个字符串ai 第N+3行包含N个整数vi 以下M行，为M次操作，操作有三种Cv x v',Cs x a',Q,第三种操作如题目描述一样，对于Test=1的修改操作，不用 做 任何变化，对于Test=2的修改操作，假设当前最后一次询问操作的答案是ans(如果还没有询问操作，ans=0),那 么对于第 一种操作中的v'=min(1000,v'+(ans mod 1000)),对于第二种操作的字符串a',它的每一位都要加上ans m od 26(a~z循环) 数据分两种，A类数据可以用离线的方法来完成，B类数据必须使用在线算法。 令len=输入数据中所有出现的字符串总长度 数据分两种，A类数据可以用离线的方法来完成，B类数据必须使用在线算法。 N<=50000,M<=10^5,Len<=10^6

输出格式

对于每一次询问输出合法的最大权字符串集合的权值和

样例输入

1
5 5
aba
ab
babb
abaa
abab
-2 1 4 2 3
Q
Cv 1 2
Q
Cs 3 abaab
Q

样例输出

4
6
9

提示

没有写明提示

题目来源

没有写明来源