P13665 「TPOI-5D」「僕は…」
题目背景
题目描述
由于你让我看到了世界的绮丽，所以需要解决一道题目。
定义 $f(a,b)$ 为字符串 $a$ 在 $b$ 中出现的次数。
给出 $n$ 个只包含小写字母的字符串 $s_1,\dots,s_n$，$q$ 次询问 $l,r,L,R$，求：
$$\sum\limits_{i=l}^r\sum\limits_{j=L}^Rf(s_i,s_j)$$
输入格式
第一行输入两个正整数 $n,q$。
接下来 $n$ 行输入 $n$ 个只包含小写字母的字符串 $s_1,\dots,s_n$。
接下来 $q$ 行输入 $q$ 个询问 $l,r,L,R$。
输出格式
输出 $q$ 个正整数，为每个询问的答案。
说明/提示
记 $m=\sum\limits_{i=1}^n|s_i|$。
| $\text{Subtask}$ | $n,m,q\le$ |特殊性质 | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $10^2$ | 无 | $5$ |
| $2$ | $2\times 10^5$ | 所有字符串均为 `a` | ^ |
| $3$ | $10^4$ | 无 | $10$ |
| $4$ | $2\times 10^5$ | 所有字符串的长度不超过 $10$ | ^ |
| $5$ | ^ | $n\le 10^2$ | ^ |
| $6$ | $5\times 10^4$ | 无 | $20$ |
| $7$ | $2\times 10^5$ | ^ | $40$ |
对于 $100\%$ 的数据，满足 $1\le n,m,q\le 2\times 10^5$，$1\le l\le r\le n$，$1\le L\le R\le n$。