CF1638E Colorful Operations
题目描述
给定一个长度为 n 的整数数组 a1,a2,…,an。初始时,每个元素的值都是 0,颜色都是 1。颜色用 1∼n 的整数表示。
你需要依次执行 q 次操作,每次操作是以下三种类型之一:
∙Color l r c:将 al,al+1,…,ar 的颜色全部改为 c,这些元素的值保持不变;
∙Add c x:将所有当前颜色为 c 的元素的值增加 x;
∙Query i:输出 ai 当前的值。
输入格式
第一行输入两个整数 n,q(1≦n,q≦106) 代表数组长度与操作次数。
此后 q 行,每行输入一个操作,格式如下:
∙若为 Color 操作,在一行上输入字符串 "Color" 和三个整数 $l,r,c\left(1 \leqq l \leqq r \leqq n;\ 1 \leqq c \leqq n\right)$;
∙若为 Add 操作,在一行上输入字符串 "Add" 和两个整数 $c,x\left(1 \leqq c \leqq n;\ -10^9 \leqq x \leqq 10^9\right)$;
∙若为 Query 操作,在一行上输入字符串 "Query" 和一个整数 i(1≦i≦n)。
操作名称按上述大小写给出,各个整数之间用一个空格分隔。
输出格式
对于每次 Query 操作,新起一行输出一个整数,代表 ai 当前的值。
测试样例
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 解释
初始时所有元素的值都是 0,颜色都是 1。各次操作后数组的状态如下:
∙执行 Color 2 4 2 后,位置 2,3,4 的颜色变为 2,值仍都是 0;
∙执行 Add 2 2 后,颜色为 2 的位置 2,3,4 的值都增加 2,变为 2;
∙执行 Query 3,输出 a3=2;
∙执行 Color 4 5 3 后,位置 4,5 的颜色变为 3,它们的值分别为 2 和 0,保持不变;
∙执行 Color 2 2 3 后,位置 2 的颜色变为 3,值仍为 2;
∙执行 Add 3 3 后,颜色为 3 的位置 2,4,5 的值都增加 3,分别变为 5,5,3;
∙执行 Query 2,输出 a2=5;
∙执行 Query 5,输出 a5=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