之前我们已经覆盖了分子生物学（DNA/RNA）、细胞生物学（细胞生命历程）、进化论（自然选择）。这一次，我们将目光转向遗传学，特别是 “多基因遗传”（Polygenic Inheritance）这一高中生物必修二中的难点和重点。

这道题目考察的是字符串处理、桶计数（Bucket Count） 以及 前缀和（Prefix Sum） 优化。难度定位 GESP 5级（约等于 CSP-J T2）。

题目：小麦的株高 (Height of Wheat)

【背景知识讲解】

在高中生物必修二《遗传与进化》中，我们学习了孟德尔的豌豆实验，那是典型的单基因遗传（比如高茎D对矮茎d是显性）。 但在自然界中，许多性状（如人的身高、皮肤颜色，小麦的株高、籽粒颜色等）并不是由一对基因决定的，而是由多对基因共同决定的。这被称为**“多基因遗传”**（Polygenic Inheritance）。

多基因遗传有以下特点：

1. 累加效应（Additive Effect）：显性基因（用大写字母表示，如 A, B, C...）对性状有增强作用。显性基因的数量越多，表现出的性状越强（例如长得越高）。
2. 不分主次：各个基因之间地位平等，AABBcc 和 aaBBCC 的表现型是一样的，因为它们都含有 4 个显性基因。
3. 环境影响：虽然题目中我们暂时忽略环境因素，只考虑基因型。

假设某种小麦的株高由 $K$ 对基因控制（例如 Aa, Bb, Cc...）。

• 基础高度为 $H_{base}$。
• 每含有一个显性基因（大写字母），株高就增加 $\Delta h$。
• 例如：基因型 AaBBcc 含有 3 个显性基因（A, B, B），其株高就是 $H_{base} + 3 \times \Delta h$。

【题目描述】

农业研究所种植了 $N$ 株小麦。为了研究遗传规律，实验员测序得到了每一株小麦的基因型字符串 $S_i$。 基因型字符串由若干对等位基因组成（如 "AaBbCC"），只包含英文字母，且保证是成对出现的（即长度为偶数）。

为了快速筛选育种，研究员需要频繁地进行 $M$ 次查询。 每次查询给出一个株高范围 $[L, R]$（闭区间），请你计算：在这 $N$ 株小麦中，有多少株的显性基因数量恰好落在 $[L, R]$ 这个范围内？

注意：

• 我们只关心显性基因的数量（即大写字母的个数）。
• 输入保证字符串长度固定为 $2 \times K$（即 $K$ 对基因）。

【输入格式】

第一行包含三个整数 $N, M, K$，分别表示小麦的株数、查询次数和基因对数。 接下来 $N$ 行，每行包含一个长度为 $2K$ 的字符串 $S_i$，表示第 $i$ 株小麦的基因型。 接下来 $M$ 行，每行包含两个整数 $L, R$，表示查询的显性基因数量范围（$0 \le L \le R \le 2K$）。

【输出格式】

对于每次查询，输出一行一个整数，表示满足条件的小麦数量。

【样例数据】

输入：

5 3 3
AaBbCc
aabbcc
AABBCC
AaBBCc
aaBbcc
1 3
0 2
4 6

输出：

2
2
2

样例解释： 共有 5 株小麦，基因对数 $K=3$（字符串长度6，最大显性数为6）。

1. AaBbCc: 大写 A, B, C，共 3 个。
2. aabbcc: 没有大写，共 0 个。
3. AABBCC: 全是大写，共 6 个。
4. AaBBCc: 大写 A, B, B, C，共 4 个。
5. aaBbcc: 大写 B，共 1 个。

统计结果（显性数 $\to$ 频率）：

• 0个: 1株 (第2株)
• 1个: 1株 (第5株)
• 3个: 1株 (第1株)
• 4个: 1株 (第4株)
• 6个: 1株 (第3株)

查询处理：

• 查询 [1, 3]: 包含显性数为 1, 2, 3 的。对应第 5 株(1个) 和 第 1 株(3个)。共 2 株。
• 查询 [0, 2]: 包含显性数为 0, 1, 2 的。对应第 2 株(0个) 和 第 5 株(1个)。共 2 株。
• 查询 [4, 6]: 包含显性数为 4, 5, 6 的。对应第 4 株(4个) 和 第 3 株(6个)。共 2 株。

【数据范围】

• 对于 100% 的数据：$1 \le N, M \le 100,000$。
• $1 \le K \le 50$（即字符串长度不超过 100，显性基因数量最大为 100）。

一、 思路提示

1. 直接暴力的局限性：
   • 如果我们对每一次查询，都去遍历这 $N$ 株小麦，检查它们的显性基因数是否在 $[L, R]$ 之间。
   • 复杂度会是 $O(M \times N)$。当 $N, M$ 都是 $10^5$ 时，总运算量达到 $10^{10}$，这在 1 秒内肯定跑不完（通常限制 $10^8$）。
2. 观察数据的特征：
   • $N$ 和 $M$ 很大，但是 $K$ 很小！
   • 显性基因的数量最多只有 $2K = 100$ 个。
   • 这意味着，虽然有 10万株小麦，但它们的“得分”（显性基因数）只有 0 到 100 这几种可能。
3. 桶排序思想 (Bucket/Frequency Array)：
   • 我们可以先遍历一遍所有小麦，统计出：显性基因为 0 的有多少株？为 1 的有多少株？... 为 100 的有多少株？
   • 存入一个数组 cnt[]，其中 cnt[x] 表示显性基因数为 x 的小麦数量。
4. 前缀和优化 (Prefix Sum)：
   • 现在的查询变成了：求数组 cnt 在下标 $[L, R]$ 区间的和。
   • 虽然区间长度很小（最多100），直接循环求和 $O(100 \times M)$ 也能过。但更优的做法是使用前缀和。
   • 构建数组 sum[i] = cnt[0] + cnt[1] + ... + cnt[i]。
   • 那么区间 $[L, R]$ 的和就是 sum[R] - sum[L-1]。
   • 这样查询复杂度降为 $O(1)$。

二、 预备知识点总结

1. 字符串遍历：判断字符是大写还是小写（'A' <= c && c <= 'Z'）。
2. 桶计数（Frequency Array）：利用数据范围较小的特性进行统计。
3. 前缀和（Prefix Sum）：经典的 $O(1)$ 解决静态区间求和问题的技巧。

三、 启发式教学：草稿纸上的推理过程

教练：“面对 10万次提问，如果你每次都去田里（数组）重新数一遍，天都要黑了。有没有办法先把数据整理好？”

1. 整理数据（预处理）：

   • 假设 $K=3$，最大得分是 6。
   • 我们画 7 个桶，编号 0 到 6。
   • 拿到第一株 AaBbCc，数一下大写字母，3个。在 3号桶 放一颗豆子。
   • 拿到第二株 aabbcc，数一下大写字母，0个。在 0号桶 放一颗豆子。
   • ... 全部放完。
   • 这时候，cnt 数组可能是：[1, 1, 0, 1, 1, 0, 1] （对应 0~6 分的株数）。

2. 回答问题：

   • 问题来了：“请问显性基因数在 1 到 3 之间的有多少？”
   • 你只需要看桶：1号桶 + 2号桶 + 3号桶。
   • 1 + 0 + 1 = 2。
   • 如果问题是 0 到 100？那就要加 100 次，稍微有点慢。

3. 进一步优化（前缀和）：

   • 我们可以做一个“累计表格” sum。
   • sum[0] = 0号桶
   • sum[1] = 0号 + 1号
   • sum[2] = 0号 + 1号 + 2号
   • ...
   • 如果问 [L, R]，其实就是 sum[R] (0到R的总数) 减去 sum[L-1] (0到L-1的总数，也就是要把左边不需要的减掉)。

4. 复杂度验证：

   • 数大写字母：$N \times 2K \approx 10^5 \times 100 = 10^7$ 次操作。很快。
   • 回答查询：$M \times 1 = 10^5$ 次操作。飞快。
   • 完全满足题目要求。

四、 读题关键词总结

1. $N, M$ 很大 $\rightarrow$ 暗示不能用双重循环，查询必须极其高效。
2. “数量” / “范围” $\rightarrow$ 典型的区间求和问题。
3. $K$ 很小 (基因对数) $\rightarrow$ “值域”很小，提示使用桶（数组）来统计频率。
4. “只关心数量” $\rightarrow$ 字符串的具体内容不重要，重要的是大写字母的个数，这是抽象建模的第一步。