#PQJ2588x15059. QOJ 2588_15059

    ID: 2841 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JSOI 2014字符串前缀和

QOJ 2588_15059

故事背景

JYY 又重新切换到计算机科学家状态并幵始研宄回文串啦!不过呢,很长的回文串对脑袋不太够用的 JYY 来说有点棘手,所以请你帮忙。

问题描述

JYY 现在有一个由小写字母组成的字符串 𝑆 。我们用 𝑆 [ 𝑖 , 𝑗 ] 表示 𝑆 中从第 𝑖 个字符到第 𝑗 个字符所组成的子串(字符串下标从1开始)。现在JYY有 𝑄 个询问,其中第 𝑖 个询问 ( 𝐿 𝑖 , 𝑅 𝑖 ) 需要统计满足如下条件的子串 𝑆 [ 𝑥 , 𝑦 ] 的数量:

𝐿 𝑖 ≤ 𝑥 ≤ 𝑦 ≤ 𝑅 𝑖 。 𝑆 [ 𝑥 , 𝑦 ] 是回文串。

请你帮助 JYY 计算这 𝑄 个询问的答案。

输入格式

输入文件的第一行包含一个字符串 𝑆 ;

第二行包含一个正整数 𝑄 ;

接下来 𝑄 行,每行两个整数 𝐿 𝑖 和 𝑅 𝑖 。

输出格式

输出包含 𝑄 行每行个一个整数,第 𝑖 行的整数为第 𝑖 个询问的答案。

样例数据 样例 1 输入 abaa 4 1 2 1 3 1 4 3 4 样例 1 输出 2 4 6 3 子任务

对于 10 % 的数据满足 𝑁 , 𝑄 ≤ 50 ;

对于 40 % 的数据满足 𝑁 ≤ 10 5 , ∑ 𝑖 ( 𝑅 𝑖 − 𝐿 𝑖 + 1 ) ≤ 10 7 ;

对于额外 20 % 的数据满足对于任意 𝑖 ,都有 𝐿 𝑖

1 或者 𝑅 𝑖

𝑁 ;

对于 100 % 的数据满足 1 ≤ 𝑁 ≤ 10 5 , 1 ≤ 𝑄 ≤ 3 ⋅ 10 5 , 1 ≤ 𝐿 𝑖 ≤ 𝑅 𝑖 ≤ 𝑁 。