A6048. 「2017 山东一轮集训 Day4」基因
编程题
省选/NOI-
知识点
题目描述
给定一个长度为 $ n $ 的字符串 $ s $，有 $ q $ 组询问，每个询问给定 $ l, r $，询问 $ s[l \ldots r] $ 中有多少本质不同的回文子串。
输入格式
第一行一个整数 $ \text{type} $，若 $ \text{type} = 0 $，表示这个数据没有进行加密，若 $ \text{type} = 1 $，表示这个数据进行了加密。
第二行两个整数 $ n, q $。
第三行一个字符串 $ s $。
接下来 $ q $ 行，每行两个整数 $ l', r' $。记 $ \text{lastAns} $ 为上一次询问的答案，若这是第一次询问，$ \text{lastAns} = 0 $，则这次猜测的 $ l, r $ 为 $ l = l' \mathbin{\text{xor}} (\text{type} \times \text{lastAns}), r = r' \mathbin{\text{xor}} (\text{type} \times \text{lastAns}) $。
第二行两个整数 $ n, q $。
第三行一个字符串 $ s $。
接下来 $ q $ 行，每行两个整数 $ l', r' $。记 $ \text{lastAns} $ 为上一次询问的答案，若这是第一次询问，$ \text{lastAns} = 0 $，则这次猜测的 $ l, r $ 为 $ l = l' \mathbin{\text{xor}} (\text{type} \times \text{lastAns}), r = r' \mathbin{\text{xor}} (\text{type} \times \text{lastAns}) $。
输出格式
输出共 $ q $ 行，代表每个询问的答案。
输入输出样例
输入 #1
1 8 4 abbabbba 1 7 3 2 6 10 1 0
输出 #1
7 2 5 2
说明/提示
对于所有数据，$n\le 100000,q\le 2n$，解密后 $1\le l\le r\le n$，字符串字符集为小写英文字母。
对于 $ 5\% $ 的数据，$ n \leq 100; \text{type} = 1 $；
对于另外 $ 15\% $ 的数据，$ n \leq 1000; \text{type} = 1 $；
对于另外 $ 15\% $ 的数据，$ n \leq 30000; \text{type} = 0 $；
对于另外 $ 15\% $ 的数据，$ n \leq 100000; \text{type} = 0 $；
对于另外 $ 50\% $ 的数据，$ n \leq 100000; \text{type} = 1 $。
对于 $ 5\% $ 的数据，$ n \leq 100; \text{type} = 1 $；
对于另外 $ 15\% $ 的数据，$ n \leq 1000; \text{type} = 1 $；
对于另外 $ 15\% $ 的数据，$ n \leq 30000; \text{type} = 0 $；
对于另外 $ 15\% $ 的数据，$ n \leq 100000; \text{type} = 0 $；
对于另外 $ 50\% $ 的数据，$ n \leq 100000; \text{type} = 1 $。