#P18346. Dictionary

Dictionary

Dictionary

题目描述

你打算在接下来的 qq 天里学习一本词典中的单词。词典用一个长度为 nn、仅由小写英文字母组成的字符串 S=s1s2⋯snS=s_1s_2\cdots s_n 表示,SS 的每个非空子串都是一个单词。相同字符串视为同一个单词,即使它在 SS 中出现了多次。

第 ii 天给定两个位置 li,ril_i,r_i。你会学习所有以

S[li:ri]=slisli+1⋯sriS[l_i:r_i]=s_{l_i}s_{l_i+1}\cdots s_{r_i}

为前缀的单词。

每天结束后,求从第一天到当前这一天为止,你已经学习了多少个不同的单词。已经学过的单词不会被重复计数。

输入格式

第一行包含一个整数 TT,表示测试数据组数。

对于每组测试数据:

第一行包含一个仅由小写英文字母组成的非空字符串 SS,其长度为 nn。

第二行包含一个整数 qq,表示学习的天数。

接下来 qq 行,第 ii 行包含两个整数 li,ril_i,r_i,表示第 ii 天学习所有以前缀 S[li:ri]S[l_i:r_i] 开头的单词。

输出格式

对每组测试数据输出一行,包含 qq 个以空格分隔的整数 c1,c2,…,cqc_1,c_2,\ldots,c_q,其中 cic_i 表示从第一天到第 ii 天为止,已经学习的不同单词数量。

数据范围

  • 1≤T≤1041\le T\le10^4;
  • 1≤n,q≤2×1051\le n,q\le2\times10^5;
  • SS 仅包含小写英文字母;
  • 1≤li≤ri≤n1\le l_i\le r_i\le n;
  • 一个输入文件内,所有测试数据的 nn 之和不超过 2×1052\times10^5;
  • 一个输入文件内,所有测试数据的 qq 之和不超过 2×1052\times10^5。

样例输入 1

2
abcabd
3
1 3
1 2
6 6
aaa
3
3 3
2 3
1 3

样例输出 1

4 6 7
3 3 3

样例说明

第一组测试数据中:

  • 第一天学习了 abc、abca、abcab、abcabd,共 44 个单词。
  • 第二天符合要求的单词为 ab、abc、abca、abcab、abcabd、abd。其中 44 个已经学过,因此累计学习 4+(6−4)=64+(6-4)=6 个不同单词。
  • 第三天学习了此前未学过的 d,累计学习 77 个不同单词。

第二组测试数据中,第一天就已经学习了 a、aa、aaa,之后的累计数量始终为 33。