题面下载

样例下载

时间限制： 4.0 秒

空间限制： 512 MB

题目背景

在曙梦研究院的硬件实验室里，资深工程师小木正在测试一条由 $n$ 个节点组成的单维全息像素阵列。为了验证该阵列在极端高频状态下的色彩稳定性，小木需要对阵列进行多次色彩相位偏移操作，并实时评估其色彩丰富度。

题目描述

给定一个长度为 $n$ 的自然数序列 $a_1,\cdots,a_n$，代表像素阵列的初始状态。序列中各元素的值只能是 $0,1,2$ 中的一个，分别代表该像素节点当前处于红（R）、绿（G）、蓝（B）三种基色状态之一。

如果阵列的一个连续像素段 $a_l,\cdots, a_r\ (1\le l\le r\le n)$ 中同时包含了 $0,1,2$ 这三种基色状态，则称像素段 $[l,r]$ 为全色域像素段，这是衡量色彩丰富度的单位指标。

测试开始后，小木会对阵列进行 $q$ 次相位偏移操作。每次操作会指定一个区间端点 $l,r\ (1\le l\le r\le n)$，该区间内的所有像素节点（即 $a_l,\cdots,a_r$）的基色状态值会提升 $1$ 个能级，并在对 $3$ 取模后循环（即色彩发生 $0 \to 1 \to 2 \to 0$ 的轮转）。

你需要在所有操作前及每次操作之后，帮助小木统计出当前时刻中整个像素序列中的全色域像素段个数。

输入格式

从标准输入读入数据。

第一行两个非负整数 $n,q$，分别表示像素阵列的长度和操作次数。

接下来一行 $n$ 个非负整数 $a_1,\cdots,a_n$，表示序列的初始基色状态。

接下来 $q$ 行，每行两个整数 $l,r$，表示每次相位偏移操作的区间端点。

输出格式

输出到标准输出。

输出 $q+1$ 行，每行一个非负整数，分别表示所有操作前及每次操作之后，对应时刻序列中全色域像素段的个数。

5 3
2 1 0 0 1
1 5
3 5
2 4

3
3
0
0

样例 1 解释

初始序列为 $[2\ 1\ 0\ 0\ 1]$，只有子区间 $[1,3],[1,4],[1,5]$ 是全色域像素段（同时包含 $0,1,2$），因此答案为 $3$。

第一次操作（区间 $[1,5]$ 状态加 $1$）后，序列变为 $[0\ 2\ 1\ 1\ 2]$，同样只有上述 $3$ 个子区间满足条件，答案为 $3$。

第二次操作（区间 $[3,5]$ 状态加 $1$）后，序列变为 $[0\ 2\ 2\ 2\ 0]$，此时无论哪个子区间都无法同时凑齐 $0,1,2$，不存在全色域像素段，答案为 $0$。

第三次操作（区间 $[2,4]$ 状态加 $1$）后，序列变为 $[0\ 0\ 0\ 0\ 0]$，依然不存在全色域像素段，答案为 $0$。

子任务

对于所有数据，保证 $1\le l\le r\le n\le 5\times 10^5,~0\le q\le 5\times 10^5,~0\le a_i\le 2$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。