#CF1638E. 颜色操作

颜色操作

CF1638E Colorful Operations

题目描述

\hspace{15pt}给定一个长度为 nn 的整数数组 a1,a2,…,ana_1,a_2,\dots,a_n。初始时,每个元素的值都是 00,颜色都是 11。颜色用 1∼n1 \sim n 的整数表示。

\hspace{15pt}你需要依次执行 qq 次操作,每次操作是以下三种类型之一:

∙ \hspace{23pt}\bullet\,Color l r c\texttt{Color } l\ r\ c:将 al,al+1,…,ara_l,a_{l+1},\dots,a_r 的颜色全部改为 cc,这些元素的值保持不变;

∙ \hspace{23pt}\bullet\,Add c x\texttt{Add } c\ x:将所有当前颜色为 cc 的元素的值增加 xx;

∙ \hspace{23pt}\bullet\,Query i\texttt{Query } i:输出 aia_i 当前的值。

输入格式

\hspace{15pt}第一行输入两个整数 n,q(1≦n,q≦106)n,q\left(1 \leqq n,q \leqq 10^6\right) 代表数组长度与操作次数。

\hspace{15pt}此后 qq 行,每行输入一个操作,格式如下:

∙ \hspace{23pt}\bullet\,若为 Color\texttt{Color} 操作,在一行上输入字符串 "Color"\texttt{"Color"} 和三个整数 $l,r,c\left(1 \leqq l \leqq r \leqq n;\ 1 \leqq c \leqq n\right)$;

∙ \hspace{23pt}\bullet\,若为 Add\texttt{Add} 操作,在一行上输入字符串 "Add"\texttt{"Add"} 和两个整数 $c,x\left(1 \leqq c \leqq n;\ -10^9 \leqq x \leqq 10^9\right)$;

∙ \hspace{23pt}\bullet\,若为 Query\texttt{Query} 操作,在一行上输入字符串 "Query"\texttt{"Query"} 和一个整数 i(1≦i≦n)i\left(1 \leqq i \leqq n\right)。

\hspace{15pt}操作名称按上述大小写给出,各个整数之间用一个空格分隔。

输出格式

\hspace{15pt}对于每次 Query\texttt{Query} 操作,新起一行输出一个整数,代表 aia_i 当前的值。

测试样例

5 8
Color 2 4 2
Add 2 2
Query 3
Color 4 5 3
Color 2 2 3
Add 3 3
Query 2
Query 5
2
5
3

样例 1 解释

\hspace{15pt}初始时所有元素的值都是 00,颜色都是 11。各次操作后数组的状态如下:

∙ \hspace{23pt}\bullet\,执行 Color 2 4 2\texttt{Color } 2\ 4\ 2 后,位置 2,3,42,3,4 的颜色变为 22,值仍都是 00;

∙ \hspace{23pt}\bullet\,执行 Add 2 2\texttt{Add } 2\ 2 后,颜色为 22 的位置 2,3,42,3,4 的值都增加 22,变为 22;

∙ \hspace{23pt}\bullet\,执行 Query 3\texttt{Query } 3,输出 a3=2a_3=2;

∙ \hspace{23pt}\bullet\,执行 Color 4 5 3\texttt{Color } 4\ 5\ 3 后,位置 4,54,5 的颜色变为 33,它们的值分别为 22 和 00,保持不变;

∙ \hspace{23pt}\bullet\,执行 Color 2 2 3\texttt{Color } 2\ 2\ 3 后,位置 22 的颜色变为 33,值仍为 22;

∙ \hspace{23pt}\bullet\,执行 Add 3 3\texttt{Add } 3\ 3 后,颜色为 33 的位置 2,4,52,4,5 的值都增加 33,分别变为 5,5,35,5,3;

∙ \hspace{23pt}\bullet\,执行 Query 2\texttt{Query } 2,输出 a2=5a_2=5;

∙ \hspace{23pt}\bullet\,执行 Query 5\texttt{Query } 5,输出 a5=3a_5=3。

2 7
Add 1 7
Query 1
Add 2 4
Query 2
Color 1 1 1
Add 1 1
Query 2
7
7
8