A6048 | $「2017 山东一轮集训 Day4」基因$

时间限制2s

内存限制512MB

通过 / 提交0/0

题目描述

给定一个长度为 $ 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}) $。

输出共 $ q $ 行，代表每个询问的答案。

输入 #1

1
8 4
abbabbba
1 7
3 2
6 10
1 0

输出 #1

C++ 编辑器

输入

输出