问题1231--不平衡的字符串

1231: 不平衡的字符串

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 1024 MB

题目描述

给出一个长度为n的字符串\(S\),以及m个约束。第\(i\)个约束要求字符串中字符\(s_i\)个数与串长之比\(k\)满足\(\frac{a}{b}<k \le \frac{c}{d}\)。求\(S\)有多少个子串至少满足这m个约束中的一个。

输入

第一行一个整数\(n\),表示字符串\(S\)的长度。
接下来一行\(n\)个字符,即字符串\(S\)。保证\(S\)只包含小写字母。
接下来一行一个整数\(m\),表示约束个数。
接下来\(m\)行,每行包括一个小写字母\(s\)及四个整数\(a,b,c,d\),表示存在一个约束,要求\(s\)在子串中出现比例处在\( (\frac{a}{b}, \frac{c}{d}] \)之间。保证\( \frac{1}{2} \le \frac{a}{b} < \frac{c}{d} \le 1 \)
对于同一个字符,不会有两个不同的约束。

输出

一个整数,表示至少满足一个约束的子串个数。

样例输入 Copy

6
aabaab
2
a 1 2 1 1
b 1 2 1 1

样例输出 Copy

17

提示

\(1\le n \le 50000\)
保证\(S\)中只含小写字母。
保证对于同一个字符,不会有两个不同的约束。
保证\( \frac{1}{2} \le \frac{a}{b} < \frac{c}{d} \le 1 \), \(1\le a,b,c,d \le 10000\)。