分数: 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