{"problem":{"name":"[ICPC 2020 Nanjing R] Baby's First Suffix Array Problem","description":{"content":" A suffix array for string $s$ of length $n$ is a permutation $sa$ of integers from $1$ to $n$ such that $s[sa_1.. n], s[sa_2..n], \\dots, s[sa_n..n]$ is the list of non-empty suffixes of $s$ sorted in","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9623"},"statements":[{"statement_type":"Markdown","content":"A suffix array for string $s$ of length $n$ is a permutation $sa$ of integers from $1$ to $n$ such that $s[sa_1.. n], s[sa_2..n], \\dots, s[sa_n..n]$ is the list of non-empty suffixes of $s$ sorted in lexicographical order. The rank table for suffixex of $s$ is a permutation $rank$ of integers from $1$ to $n$ such that $rank_{sa_i} = i$.\n\nKotori has a string $s=s_1s_2\\dots s_n$. She would like to ask $m$ queries. And in the $i$-th query, a substring $x=s[l_i..r_i]$ of $s$ is given, Kotori would like to know the rank of suffix $s[k_i..r_i]$ of $x$.\n\nNote $s[l..r]$ means the substring of $s$ which starts from the $l$-th position and ends at the $r$-th position, both inclusive.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n$ and $m$ ($1 \\le n, m \\le 5 \\times 10^4$) -- the length of the string and the number of queries.\n\nThe second line contains a string $s$ of length $n$ consisting only of lowercase English letters.\n\nEach of the next $m$ lines contains three integers $l_i$, $r_i$ and $k_i$ ($1 \\le l_i \\le r_i \\le n, l_i \\le k_i \\le r_i$) denoting a query.\n\nIt is guaranteed that neither the sum of $n$ or the sum of $m$ of all test cases will exceed $5 \\times 10^4$.\n\n## Output\n\nFor each query output one line containing one integer denoting the answer.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9623","tags":["字符串","2020","O2优化","ICPC","南京"],"sample_group":[["2\n10 4\nbaaabbabba\n2 8 3\n1 1 1\n2 3 2\n2 5 4\n20 3\ncccbccbadaacbbbcccab\n14 17 16\n3 20 17\n17 20 18\n","2\n1\n2\n3\n4\n15\n3\n"]],"created_at":"2026-03-03 11:09:25"}}