CF138E Hellish Constraints

Katya 最近开始出编程题并准备自己的比赛。她不喜欢枯燥简单的限制条件。Katya 已经厌倦了那些“$N$ 不超过一千”和“$a_i$ 的和不超过一百万”之类的条件，于是她决定想出一些更复杂的限制。 Katya 最近写的最后一道题与字符串有关。输入是一个由小写拉丁字母组成的字符串。为了让题目描述更长、让参赛者望而生畏，Katya 想出了如下 $k$ 个相同类型的限制（限制中的字符可以重复，某些限制之间也可能互相矛盾）： - 字符串中字符 $c_1$ 的数量不少于 $l_1$ 且不多于 $r_1$。 - ... - 字符串中字符 $c_i$ 的数量不少于 $l_i$ 且不多于 $r_i$。 - ... - 字符串中字符 $c_k$ 的数量不少于 $l_k$ 且不多于 $r_k$。 然而，Katya 觉得这样还太简单明显，于是又加了一个条件：一个字符串需要满足上述 $k$ 个限制中不少于 $L$ 个且不多于 $R$ 个限制。 Katya 不喜欢出太难太刁钻的测试数据，所以她直接取了一个很大的字符串 $s$，想把所有满足条件的子串都加入测试数据中。然而，Katya 被自己的条件搞晕了，于是请你帮她统计字符串 $s$ 中有多少个子串满足这些条件（每个子串的出现都要单独计数）。

第一行包含一个非空字符串 $s$，由小写拉丁字母组成。字符串 $s$ 的长度不超过 $10^5$。 第二行包含三个用空格分隔的整数 $k$、$L$ 和 $R$（$0 \leq L \leq R \leq k \leq 500$）。 接下来的 $k$ 行，每行包含 Katya 的一个限制，格式为 “$c_i$ $l_i$ $r_i$”。所有 $c_i$ 均为小写拉丁字母，$l_i$ 和 $r_i$ 为整数（$0 \leq l_i \leq r_i \leq |s|$，其中 $|s|$ 表示字符串 $s$ 的长度）。字母 $c_i$ 不一定互不相同。

输出一个整数，表示满足限制条件的子串数量。 请不要在 C++ 中使用 %lld 格式符来读写 64 位整数。建议使用 cout 流或 %I64d 格式符。

在第一个测试样例中，我们需要统计不包含字符 “e” 和 “o” 的子串数量。所有这样的子串如下（按在原字符串中从左到右出现的顺序）："c", "d", "f", "r", "rc", "c", "s"。 在第二个测试样例中，无法恰好满足两个完全相同的限制中的一个，因此答案为 0。 由 ChatGPT 4.1 翻译