首页 > 试题广场 >

小美的彩带

[编程题]小美的彩带
  • 热度指数：2041 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小美的彩带是由一条长度为 n 的彩带一直无限循环得到的，彩带的每一个位置都有一个颜色，用 a_i 表示。因此当 i>n 时， a_i=a_{i-n} 。

小美每次会从左往右或从右往左剪一段长度为 x 的彩带，她想知道她每次剪下来的彩带有多少种颜色。


输入描述:
\,\,\,\,\,\,\,\,\,\,第一行输入两个整数 n,q\left(1 \leq n,q \leq 2 \times 10^5\right) 代表彩带长度、剪彩带次数。
\,\,\,\,\,\,\,\,\,\,第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(1 \leq a_i \leq 10^9\right) 代表彩带每一个位置的颜色。
\,\,\,\,\,\,\,\,\,\,此后 q 行，每行输入一个字符 c 和一个整数 x\left(1 \leq x \leq 10^9;\ c\in {\tt 'L'} , {\tt 'R'}\right) 代表裁剪方向和裁剪长度，其中 '\tt L' 说明从左往右剪， '\tt R' 说明从右往左剪 。


输出描述:
\,\,\,\,\,\,\,\,\,\,对于每一次裁剪彩带，在一行上输出一个整数代表颜色数量。
示例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\} 这一种颜色。
算法知识视频讲解
开通博客

暂无题解

问题信息

难度：
12条回答 2905浏览

热门推荐

相关试题

小美的彩带

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号