#PQJ1973x10356. QOJ 1973_10356
QOJ 1973_10356
标题: 基因序列 - Problem - QOJ.ac
#10356. 基因序列
The problem was used in the following contests:
Srwudi 是一个顶级生物科学家,他参与了很多基因工程工作。其中的一个工程需要研究某个物种基因片段的数目,也就是说,会有一个经过处理的样本DNA串 S,S 的每一个子串都可能是一个基因。对于某个子串 S[l..r],表示S中第 l 个字符到第 r 个字符组成的串,假如S[l..r]是一个回文串(一个串T为回文串,当且仅当将 T 翻转后,仍与原串相同),那么 S[l..r] 就是一个基因。注意,不同的基因可能重叠。比如说aba,就有4个基因,S[1..1]=a,S[2..2]=b,S[3..3]=c,S[1..3]=aba。但一个串S中可能含有很多功能相同的基因,对于两个基因 T,P,将他们视为两个字符串,他们只需要满足一下条件中的一个,那么就是不同的:
- T的长度≠P的长度
- 存在一个位置j,满足T[j]≠P[j],其中T[j],P[j]表示分别在位置j上的字符。
比如对于 aba,就只有 3 个功能不同的基因了。对于一个 DNA,Srwudi 想知道这个 DNA 串中会含有多少功能不同的基因。
但研究往往是困难重重的,由于技术有限,Srwudi提取样本串 S 时不能保证十分精确,甚至有可能这个串S会是很多个DNA片段缠绕在一起的。因此,Srwudi首先将提取出来的东西展开成一条长度为 N 的链,设为 A,注意 A 依然是一个串,Srwudi接下来会进行 Q 次猜测,每次他会选择一段 A 中的子串 A[l..r],并认为这就是一段合法的 DNA,然后算出 A[l..r] 中有多少功能不同的基因,假如 Q 足够大并且 Srwudi 的猜测足够准确的话,这个基因工程就能继续推进了。
然而,正当 Srwudi 准备开始工作时,他意识到一个困难,他无法快速地知道一个串 S 中会有多少功能不同的基因,所以他找到了你,希望你能帮助他。 由于 Srwudi 的猜测不是盲目性的,他每次猜测后获得的数据会影响下一次的猜测,因此部分输入数据会进行一定的加密。
输入格式
第一行一个整数 type,若 type=0,表示这个数据没有进行加密,若 type=1,表示这个数据进行了加密。
第二行两个整数 N,Q,表示样本 A 的长度为 N,以及Srwudi进行的猜测次数为 Q。 接下来 Q 行,每行两个整数 L′,R′。记 lastans 为上一次猜测的答案,若这是第一次猜测,则 lastans=0,则这次猜测的L,R为,L=L′⊕(type×lastans),R=R′⊕(type×lastans)。
输出格式
输出 Q 行,每行一个整数,表示对于这次猜测,A[L..R] 中含有的功能不同的基因数目。
样例数据
样例输入
1
8 4
abbabbba
1 7
3 2
6 10
6 0
样例输出
7
2
5
3
样例解释
解密后的猜测依次为:
1 7
猜测的子串为abbabbb,不同功能的基因分别是:a,b,bb,bab,bbb,abba,bbabb
4 5
猜测的子串为ab,不同功能的基因分别是:a,b
4 8
猜测的子串为abbba,不同功能的基因分别是:a,b,bb,bbb,abbba
3 5
猜测的子串为bab,不同功能的基因分别是:a,b,bab
数据范围
对于所有数据,满足Q≤2N,且解密后的L,R,满足1≤L≤R≤N
数据点编号 N 的大小不超过 type 的取值 1 100 1 2 1000 3 4 5 30000 0 6 7 8 100000 9 10 11 1 12 13 14 15 16 17 18 19 20