QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 532. 区间本质不同子串

统计

题目描述

给定字符串 $S$,$q$ 次询问,每次给出 $l,r(1 \leq l \leq r \leq |S|)$,你需要求出 $S[l:r]$ 本质不同的子串数量。

输入格式

输入的第一行包含一个字符串 $S$。

接下来一行包含一个整数 $q$。

接下来 $q$ 行,每行两个整数 $l,r$,描述一组询问。

输出格式

输出 $q$ 行,每行一个整数,表示答案。

样例数据

样例 1 输入

helloeveryonenationalolympiadininformaticswilltakeplaceinaugustgoodlucktoeveryonebythewaythisisejudgecontestadministrationsystem
5
1 58
18 46
35 57
25 40
55 56

样例 1 输出

1662
420
267
129
3

样例 2 输入

browseprivatelyexplorefreelydefendyourselfagainsttrackingandsurveillancecircumventcensorship
5
1 30
15 45
20 60
30 70
40 80

样例 2 输出

447
476
830
832
832

样例 3

见下发文件

子任务

对于所有数据,$1 \leq |S| \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5$。

  • Subtask 1(5 Points): $|S|,q \leq 50$
  • Subtask 2(20 Points): $q \leq 50$
  • Subtask 3(26 Points): $S$ 中只含有 ab
  • Subtask 4(23 Points): $|S| \leq 2 \times 10^4, q \leq 4 \times 10^4$
  • Subtask 5(26 Points): 没有额外的限制。