题目描述： 小A有很多双手套，但是由于他不是很爱收拾所以现在这些手套全部乱成一团。小A的手套是不分左右手的，但是需要两只相同花色的手套才能匹配成一双。小A现在将这些手套排成一行，他想知道如果将区间 [1 r] 中的所有手套取出，且r-1+1 是偶数，这些手套是否刚好能组成 (r-1+1)/2 双手套。小A会提出这个问题很多次，你能帮帮他吗? 输入描述 输入的第一行包含两个整数n (2<=n<=10)和q (1<=q<=10°)，表示小A手中的手套数量和询问次数。接下来一行包含n个整数，其中第i个表示第i只手套的花色编号。（保证花色编号是一个 [1, 65536] 之间的整数）接下来q行每行两个整数I和r(1<=l<r<=n)，表示小A的询问 区间。保证r-l+1是一个偶数。 输出描述 对于每一次询问，如果Lr]中所有手套能够刚好组成(r-l+1)/2双，输出一行“yes”否则输出”no”。（输出时均不包含引号 且均为小写）

这是一个典型的涉及数组、频率统计及区间查询的问题。以下是针对该问题的详细解答： --- ### 解题思路 1. **理解题目需求** - 给定一组手套的颜色编号序列，需要判断任意一个区间 `[l, r]` 内的手套能否恰好配成 `(r-l+1)/2` 对。 - 手套无左右之分，并且只有颜色完全相同的两只才能配成一对。 2. **关键点分析** - 区间内每种手套的数量如果是奇数，则无法完全配对；换句话说，区间的总手套数减去两倍的已配对手套数应为零。 - 使用哈希表（字典）记录每个颜色出现的频次是一种有效的方法。 3. **算法设计** - 初始化一个空的哈希表 `color_count` 记录颜色及其对应的数量。 - 针对每一个询问区间 `[l, r]`： 1. 清空当前哈希表。 2. 遍历从位置 `l` 到位置 `r` 的所有手套，更新对应颜色的计数。 3. 检查是否满足条件：`(r-l+1)` 减去所有颜色中最大可能配对数的总数等于零。 - 最大可能配对数计算公式为：对于某种颜色有 `k` 只手套，则最多可以配对 `floor(k / 2)` 对。 4. **优化方向** - 因为本题的数据范围较小 (`n <= 10`) ，直接暴力枚举可行。 - 若数据量增大，可考虑前缀和或莫队等更高效的区间求解技术提升性能。 --- ### 示例代码实现 (Python) 下面是基于上述思想的一个完整 Python 实现： ```python from collections import defaultdict def solve_gloves_problem(n, q, gloves, queries): results = [] for l, r in queries: color_count = defaultdict(int) # 统计[l, r]范围内各颜色手套的数量 for i in range(l-1, r): # 注意索引转换：用户输入的是1-based index color_count[gloves[i]] += 1 total_pairs = 0 glove_sum = r - l + 1 # 获取区间内的手套总数 # 根据每种颜色的最大配对数目累加 for count in color_count.values(): total_pairs += count // 2 if total_pairs * 2 == glove_sum: # 看看实际能组多少双 results.append("yes") else: results.append("no") return results # 输入部分模拟开始 if __name__ == "__main__": n, q = map(int, input().split()) gloves = list(map(int, input().split())) queries = [tuple(map(int, input().split())) for _ in range(q)] answers = solve_gloves_problem(n, q, gloves, queries) print("\n".join(answers)) ``` --- ### 时间复杂度分析 1. **单次询问**：假设平均每次询问处理约一半的数据规模即 `m ≈ n/2`, 其中最坏情况下的时间复杂度大约为 \(O(m)\), 即 O((n^2)。 2. **整体复杂度**: 查询次数为q时的整体复杂度约为 O(q \* (n^2)). 由于题目限制了\(n ≤ 10\) 和 \(q ≤ 10\), 整体运行效率是可以接受的。 ---