← 返回题目列表

AtCoder · awc0017_c

C. 花坛里的同色检查

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥负责管理学校的花坛。 N 地块排列成一行,并且 i左边第一个图 (1 \leq i \leq N)有一朵彩色的花 C_i 种植在其中。这里,花的颜色用正整数表示。

青木问高桥 Q 调查花坛外观的问题。在花坛中,如果相邻两块地都有相同颜色的花朵,视觉上的变化很小,显得单调。因此,青木想知道指定范围内有多少个地方有相同花色的相邻地块。

在 j第一个问题(1 \leq j \leq Q),绘图的范围 L_j 绘制 已指定 R_j 。求整数的个数 i 满意 L_j \leq i \leq R_j - 1 和 C_i = C_{i+1}。换句话说,在图的连续间隔内的相邻图对之间 L_j 绘制 已指定 R_j,计算花朵颜色匹配的对数。

找出每个问题的答案 Q 问题。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j < R_j \leq N (1 \leq j \leq Q)
  • 所有输入值均为整数。

输入

N Q
C_1 C_2 \ldots C_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 第一行包含整数 N 代表绘图数和整数 Q 代表问题数量,以空格分隔。
  • 第二行包含整数 C_1, C_2, \ldots, C_N 代表每个地块的花朵颜色,以空格分隔。
  • 如下 Q 行, j第行包含左端点 L_j 和右端点 R_j 中指定的范围 j第一个问题,用空格分隔。

输出

输出 Q 行。上 j第行(1 \leq j \leq Q),输出答案 j第题,即整数的个数 i 满意 L_j \leq i \leq R_j - 1 和 C_i = C_{i+1}.


示例输入 1

5 3
1 1 2 2 2
1 5
1 3
3 5

示例输出 1

3
1
2

示例输入 2

8 5
3 3 3 1 2 2 1 1
1 8
2 5
1 4
5 8
3 6

示例输出 2

4
1
2
2
1

示例输入 3

15 8
10 10 5 5 5 3 3 7 7 7 7 1 1 2 2
1 15
1 5
5 10
10 15
3 7
2 14
6 8
1 2

示例输出 3

9
3
3
3
3
7
1
1