P6152 [CTT Homework 2018] Number of Suffix Tree Nodes

Source: Chen Jianglun, 2018 Candidate Team paper.

Given a string $P$ of length $n$, there are $m$ queries. Each query gives two parameters $l, r$ and asks for the number of nodes in the suffix tree built from the substring $P[l,r]$. If you do not know what a suffix tree is, you can also understand it as building a suffix automaton on the reversed string of $[l,r]$. Note that in this problem, the root node of the suffix tree is not included in the answer.

In this problem, the string is represented by numbers. Different numbers represent different characters, and the same number represents the same character. The numbers are in the range $[0,n]$. The first line contains two positive integers $n$ and $m$, representing the length of the string and the number of queries. The second line contains $n$ non-negative integers separated by spaces, representing the string. The next $m$ lines each contain two positive integers $l, r$, representing a query: ask for the number of nodes in the suffix tree of the substring $[l,r]$.

Output $m$ lines. Each line contains one positive integer representing the answer.

For $30\%$ of the testdata: $n,m\le 3\times 10^3$. For $100\%$ of the testdata: $n\le 10^5$, $m\le 3\times 10^5$, and each number in the string is $\le n$。 Translated by ChatGPT 5