「Codeforces 1073G」Yet Another LCP Problem
题目链接:Codeforces 1073G
定义 $\text{LCP}(s, t)$ 字符串 $s$ 和 $t$ 的最长公共前缀,再定义 $s[x\dots y]$ 为字符串 $s$ 从位置 $x$ 到 $y$ 的子串。
给定一个长度为 $n$ 的字符串 $s$ 和 $q$ 个询问。每次询问给出两个长度分别为 $k_i, l_i$ 的序列 $a, b$。你需要计算 $\sum_{i = 1} ^ k \sum_{j = 1} ^ l \text{LCP}(s[a_i \dots n], s[b_j \dots n])$ 的值。
数据范围:$1 \le n, q, \sum k_i, \sum l_i \le 2 \times 10 ^ 5$,$1 \le k_i, l_i \le n$。