小美的彩带是由一条长度为 n 的彩带一直无限循环得到的，彩带的每一个位置都有一个颜色，用 a_i 表示。因此当 i>n n" style="text-wrap:wrap;" /> 时， a_i=a_i-n 。 小美每次会从左往右或从右往左剪一段长度为 x 的彩带，她想知道她每次剪下来的彩带有多少种颜色。
第一行输入两个整数 n,q(1 ≤ n,q ≤ 2 × 10^5) 代表彩带长度、剪彩带次数。 第二行输入 n 个整数 a_1,a_2,...,a_n(1 ≤ a_i ≤ 10^9) 代表彩带每一个位置的颜色。 此后 q 行，每行输入一个字符 c 和一个整数 x(1 ≤ x ≤ 10^9;c∈ 'L' , 'R') 代表裁剪方向和裁剪长度，其中 ' L ' 说明从左往右剪， ' R ' 说明从右往左剪 。
对于每一次裁剪彩带，在一行上输出一个整数代表颜色数量。
6 4 1 1 4 5 1 4 L 2 L 3 R 12 R 1
1 3 3 1
考点：前缀和
数据规模 n ≤ 200000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
推荐方向：前缀和
本题切入点
彩带无限循环且每次剪的长度 x 可达 1e9，先按周期把 x 化简成前缀/后缀区间；预处理每个前缀（后缀）位置的不同颜色数，查询即可 O(1) 回答，整体 O(n+q)。
预处理前缀和数组，把「区间求和」从 O(n) 降到 O(1)。
思路框架（前缀和 通法 · 非本题专属）
实现要点：开 long long，避免 n 较大时求和溢出。
复杂度：时间 预处理 O(n)，每次查询 O(1) ｜ 空间 O(n)
该范式的通法易错点
对照本题
样例 1：输入 6 4 / 1 1 4 5 1 4 / L 2 / L 3 / R 12 / R 1 → 输出 1 / 3 / 3 / 1
第一次剪彩带，剪下来的是 [1,1] ，有 \1 这 1 种颜色；
第二次剪彩带，剪下来的是 [4,5,1] ，有 \1,4,5 这 3 种颜色；
第三次剪彩带，剪下来的是 [4,1,5,4,1,1,4,1,5,4,1,1] ，有 \1,4,5 这 3 种颜色。
第四次剪彩带，剪下来的是 [4] ，有 \4 这一种颜色。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2024年秋招-美团-技术岗-第一批笔试。