You are given a string s of length n, consisting of first k lowercase English letters.
We define a c-repeat of some string q as a string, consisting of c copies of the string q. For example, string "acbacbacbacb" is a 4-repeat of the string "acb".
Let's say that string a contains string b as a subsequence, if string b can be obtained from a by erasing some symbols.
Let p be a string that represents some permutation of the first k lowercase English letters. We define functiond(p) as the smallest integer such that a d(p)-repeat of the string p contains string s as a subsequence.
There are m operations of one of two types that can be applied to string s:
- Replace all characters at positions from li to ri by a character ci.
- For the given p, that is a permutation of first k lowercase English letters, find the value of function d(p).
All operations are performed sequentially, in the order they appear in the input. Your task is to determine the values of function d(p) for all operations of the second type.
The first line contains three positive integers n, m and k (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 20000, 1 ≤ k ≤ 10) — the length of the string s, the number of operations and the size of the alphabet respectively. The second line contains the string s itself.
Each of the following lines m contains a description of some operation:
- Operation of the first type starts with 1 followed by a triple li, ri and ci, that denotes replacement of all characters at positions from li to ri by character ci (1 ≤ li ≤ ri ≤ n, ci is one of the first klowercase English letters).
- Operation of the second type starts with 2 followed by a permutation of the first k lowercase English letters.
For each query of the second type the value of function d(p).
7 4 3 abacaba 1 3 5 b 2 abc 1 4 4 c 2 cba
6 5
After the first operation the string s will be abbbbba.
In the second operation the answer is 6-repeat of abc: ABcaBcaBcaBcaBcAbc.
After the third operation the string s will be abbcbba.
In the fourth operation the answer is 5-repeat of cba: cbAcBacBaCBacBA.
Uppercase letters means the occurrences of symbols from the string s.
题目大意：给出一个包含前$k$个小写字母，长度为$n$的字符串$s$。有$m$个操作，操作有两种类型。对于第一种操作，给出$l_i,r_i,c_i$，表示把$s_l$到$s_r$之间的所有字母改成$c_i$。对于第二种操作，给出一个前$k$个小写字母的排列$p$，求最小的整数$x$，使得$s$是$p$重复$x$次（即$x$个$p$连接起来）所得字符串的子序列（不连续）。
显然询问的答案是满足$s_{i+1}$在$p$中的下标不超过$s_i$在$p$中下标的$i$的个数。
开一颗线段树，在每个节点维护一个矩阵$A$，其中$a_{i,j}$表示该节点对应的子串中连续字符$i,j$的出现次数。
因为$k\leq 10$，所以效率没有问题。
代码在此。
评论 (0)
