题目分析

球在 X 轴上从 0 出发向右运动，遇到墙则反弹。墙分为两类：

• R 类墙：位于 len, 2*len, 3*len, ..., freq*len 位置
• L 类墙：位于 -len, -2*len, -3*len, ..., -freq*len 位置

每个坐标可能有多堵墙，但每次撞击只破坏一堵。给定多个时间 T，求球的位置。

核心思路

1. 运动规律

球在左右墙之间来回反弹。设：

• 第 k 次撞击前，球已移动的总距离为 dist[k]
• 第 k+1 次撞击的墙位置为 next_wall[k]

则球的运动是分段线性函数，可以通过二分确定在给定时间 T 时处于哪一段。

2. 数据结构设计

类 A 用于管理一类墙（L 或 R）：

• walls：存储所有墙的 (len, freq) 对
• cnt[i]：位置 ≤ i 的墙的数量
• sum[i]：位置 ≤ i 的墙的位置和
• sum2：存储大位置墙的位置前缀和（用于位置 > sqrt(T) 的墙）

3. 预处理

3.1 小位置墙（≤ sqrt(T)）

直接枚举所有可能位置，统计每个位置的墙数量和位置和。

3.2 大位置墙（> sqrt(T)）

使用优先队列按 cur*len 排序，逐步生成墙位置的前缀和。

4. 查询处理

对于给定的 T：

1. 二分撞击次数 k：找到最大的 k 使得 dist_L[k] + dist_R[k] ≤ T
2. 计算剩余时间：T_remaining = T - (dist_L[k] + dist_R[k])
3. 确定位置：
   • 如果在向右移动段：位置 = T_remaining
   • 如果在向左移动段：位置 = 2*wall_R - T_remaining
   • 如果在返回向右段：位置 = T_remaining - 2*(wall_R + wall_L)

算法复杂度

• 预处理：O(N + sqrt(T) log N)
• 每次查询：O(log N × log T)
• 总复杂度：O(N + Q log N log T)

关键优化

1. 分离大小位置：将墙按位置大小分开处理，避免处理大量大数值
2. 前缀和加速：通过预处理前缀和快速计算总移动距离
3. 二分查找：快速定位撞击次数
4. 查询缓存：对频繁查询的 k 值缓存结果

样例验证

对于样例输入：

3 12
R 3 2
R 6 1
L 3 2
0
1
2
3
4
5
6
7
17
18
19
200

程序正确输出：

0
1
2
3
2
1
0
-1
5
6
5
-152

与题目样例完全一致。

总结

本题通过巧妙的预处理和二分查找，将看似复杂的物理运动问题转化为可计算的数据结构问题。核心在于将墙按位置大小分类处理，并利用前缀和快速计算球的运动轨迹。