小美的彩带
美团 2024 秋招笔试编程题 · 循环数组 + 离线树状数组
题目描述
小美的彩带是由一条长度为 n 的彩带一直无限循环得到的，彩带的每一个位置都有 一个颜色，用 a[i] 表示。因此当 i > n 时，a[i] = a[i-n]。
小美每次会从左往右或从右往左剪一段长度为 x 的彩带， 她想知道她每次剪下来的彩带里有多少种颜色。
输入格式
第一行两个整数 n、q，代表彩带长度、剪彩带次数。
第二行 n 个整数 a[i]，代表彩带每一个位置的颜色。
此后 q 行，每行输入一个字符 c 和一个整数 x，代表裁剪方向和裁剪长度，
其中 L 说明从左往右剪，R 说明从右往左剪。
输出格式
对于每一次裁剪，在一行上输出一个整数，代表剪下来的彩带中不同颜色的数量。
示例
示例 1
输入：
6 4
1 1 4 5 1 4
L 2
L 3
R 12
R 1
输出：
1
3
3
1
说明：
彩带为 1 1 4 5 1 4。
- 第 1 次
L 2：从最左边剪 2 个 →[1,1]，1 种颜色； - 第 2 次
L 3：接着第 1 次往右剪 3 个 →[4,5,1]，3 种颜色； - 第 3 次
R 12：从最右边往左剪 12 个，覆盖了完整周期 → 3 种颜色； - 第 4 次
R 1：接着第 3 次往左剪 1 个 →[4]，1 种颜色。
解题思路
第一步：关键的语义 —— 裁剪位置是累积的
这题最容易错的地方：同方向的多次裁剪是首尾相接的。
- 第 i 次
L剪的那一段，紧挨在第 i-1 次L的右边； - 第 i 次
R剪的那一段，紧挨在第 i-1 次R的左边； L和R各自维护一个指针，互不影响。
用两个指针模拟：
left → L 序列当前的下一个起点
right → R 序列当前的下一个终点
出发时 left 指向彩带开头、right 指向彩带结尾；指针越界时按周期
平移回 1..n 内（while left > n: left -= n）。
第二步：把环「剪断」成倍增数组
彩带是无限循环的，直接处理很别扭。把原彩带复制一份接在后面，
得到长度为 2n 的数组 —— 所有长度不超过 n 的裁剪段都能在里面
找到一个普通区间来对应。
第三步：区间不同颜色数 —— 离线 + 树状数组
剩下的问题是「求许多区间 [l, r] 内不同颜色数」，经典套路：
- 把查询按右端点 r 升序排序；
- 从左往右扫数组，树状数组里只保留每种颜色当前最后一次出现的位置
（出现新的就把旧的
-1，新的位置+1）； - 扫到某个查询的 r 时，答案 =
sum(r) - sum(l-1)： 在[l, r]内只统计「最后一次出现」落在区间里的颜色，恰好每种颜色一次。
因为答案只依赖「每个颜色最后一次出现的位置」，把查询离线排序后，
树状数组可以一边扫一边答，总复杂度 O((n + q) log n)。
颜色值可能很大（到 1e9），先离散化即可。
完整代码实现
算法可视化 · 逐帧回放这道题的代码407 帧 · 录制输入
import sys
def solve() -> None:
"""离线树状数组求倍增数组上的区间不同颜色数"""
data = sys.stdin.read().split()
if not data:
return
idx = 0
n = int(data[idx]); q = int(data[idx + 1]); idx += 2
colors = data[idx:idx + n]; idx += n
# 颜色离散化
comp = {v: i for i, v in enumerate(sorted(set(colors)))}
arr = [comp[v] for v in colors]
doubled = arr + arr
size = 2 * n
# 累积指针：L 从左往右推进，R 从右往左回退（下标 0 起）
left = 0
right = size - 1
queries = [] # (l, r, query_index)
for qi in range(q):
c = data[idx]; x = int(data[idx + 1]); idx += 2
if c == 'L':
while left >= n:
left -= n
l = left
r = min(left + x - 1, size - 1)
queries.append((l, r, qi))
left = l + x
else: # 'R'
while right < n:
right += n
r = right
l = max(right - x + 1, 0)
queries.append((l, r, qi))
right = l - 1
# 树状数组（下标 1 起）
bit = [0] * (size + 1)
def add(i: int, v: int) -> None:
i += 1
while i <= size:
bit[i] += v
i += i & -i
def prefix(i: int) -> int:
i += 1
s = 0
while i > 0:
s += bit[i]
i -= i & -i
return s
ans = [0] * q
last = {}
ptr = 0
for l, r, qi in sorted(queries, key=lambda t: t[1]):
while ptr <= r:
col = doubled[ptr]
if col in last:
add(last[col], -1)
last[col] = ptr
add(ptr, 1)
ptr += 1
ans[qi] = prefix(r) - (prefix(l - 1) if l > 0 else 0)
sys.stdout.write("\n".join(map(str, ans)) + "\n")
if __name__ == "__main__":
solve()
示例推演
彩带 a = [1,1,4,5,1,4]，倍增后：
下标(0起): 0 1 2 3 4 5 6 7 8 9 10 11
值 : 1 1 4 5 1 4 1 1 4 5 1 4
指针初始 left = 0、right = 11：
| 查询 | 指针处理 | 区间 | 颜色数 |
|---|---|---|---|
| L 2 | left=0 → 区间 [0,1]；left 变成 2 | [1,1] | 1 |
| L 3 | left=2 → 区间 [2,4]；left 变成 5 | [4,5,1] | 3 |
| R 12 | right=11 → 区间 [max(0,0),11]；right 变成 -1 | 全部 | 3 |
| R 1 | right=-1 → 平移为 11 → 区间 [11,11]；right 变成 10 | [4] | 1 |
与样例输出一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 每个区间 set 去重 | O(q * x) | O(n) | x 可达 1e9，必超时 |
| 离线 + 树状数组 | O((n + q) log n) | O(n + q) | 推荐 |
易错点总结
1. 把同方向的裁剪当成「各自独立」
最容易错的一点：L 2 和 L 3 剪的不是同一段的前几个，
而是首尾相接的两段。必须用指针累积推进。
2. 指针越界没有平移
left 会一路增大、right 会一路减小，超过 1..n 范围时要按周期
平移（-n / +n），否则下标会越界或指错位置。
3. 颜色值没有离散化
颜色可以到 1e9，直接用值当下标会越界；离散化后范围是 0..n-1。
4. 忘记「答案只跟最后一次出现有关」
区间不同颜色数的标准技巧是「只保留最后一次出现的位置」。 如果对每个查询重新去重，复杂度会退化。
扩展思考
- 如果把「不同颜色数」换成「出现次数最多的颜色频率」，就要用莫队等其它做法。
- 「区间不同数」的在线做法可以用主席树，代价是更高空间。