题目大意

有 $N$ 个地铁站，每个站属于 $M$ 条环形线路之一。每个站有初始志愿者数 $C_i$。支持两种操作：

查询区间 $[l, r]$ 内所有站的志愿者数之和

将某条线路上的所有列车移动到下一站（循环移位）

要求高效处理 $Q$ 个操作。

算法思路

核心思想

分块处理 + 双指针预处理，根据线路大小采用不同策略。

关键观察

操作 2 相当于对整条线路进行循环移位

直接模拟每次移位再查询会超时

需要维护每个位置的当前志愿者数

分块策略

1. 小线路（大小 ≤ B）

使用分块数组直接维护每个位置的志愿者数

更新时直接修改块内和

查询时遍历相关块

2. 大线路（大小 > B）

预处理该线路所有站点的前缀和（复制两份处理环形）

维护该线路的累计移位量 $D$

查询时通过双指针找到区间端点在线路中的位置

利用前缀和 $O(1)$ 计算区间和

算法流程

预处理

统计每条线路包含的站点

初始化分块数组（小线路）

预处理大线路的前缀和

处理操作

对于小线路的移位：直接更新分块数组

对于大线路的移位：仅记录移位次数

对于查询：

小线路贡献：从分块数组查询

大线路贡献：通过前缀和计算

双指针优化

预处理每个位置在所属线路中的下一个/上一个站点

快速定位查询区间在线路中的范围

复杂度分析

时间复杂度：$O((N+Q)\sqrt{N})$，分块的标准复杂度

空间复杂度：$O(N)$，存储线路信息和前缀和

总结

本题是分块思想的经典应用：

按数据规模分类处理：小数据直接维护，大数据预处理

分块数组：平衡更新和查询的复杂度

循环移位处理：通过记录移位次数而非实际移动数据来优化

双指针技巧：快速定位区间在线路中的位置

这种"根据规模选择策略"的方法在处理不均匀数据时非常有效，体现了分块技术在解决复杂操作问题中的灵活性。