A14954. Colorful Operations
编程题
普及/提高-
知识点
题目描述
You have an array $a_1,a_2, \dots, a_n$ . Each element initially has value $0$ and color $1$ . You are also given $q$ queries to perform:
- Color $l$ $r$ $c$ : Change the color of elements $a_l,a_{l+1},\cdots,a_r$ to $c$ ( $1 \le l \le r \le n$ , $1 \le c \le n$ ).
- Add $c$ $x$ : Add $x$ to values of all elements $a_i$ ( $1 \le i \le n$ ) of color $c$ ( $1 \le c \le n$ , $-10^9 \le x \le 10^9$ ).
- Query $i$ : Print $a_i$ ( $1 \le i \le n$ ).
- Color $l$ $r$ $c$ : Change the color of elements $a_l,a_{l+1},\cdots,a_r$ to $c$ ( $1 \le l \le r \le n$ , $1 \le c \le n$ ).
- Add $c$ $x$ : Add $x$ to values of all elements $a_i$ ( $1 \le i \le n$ ) of color $c$ ( $1 \le c \le n$ , $-10^9 \le x \le 10^9$ ).
- Query $i$ : Print $a_i$ ( $1 \le i \le n$ ).
输入格式
The first line of input contains two integers $n$ and $q$ ( $1 \le n,q \le 10^6$ ) — the length of array $a$ and the number of queries you have to perform.
Each of the next $q$ lines contains the query given in the form described in the problem statement.
Each of the next $q$ lines contains the query given in the form described in the problem statement.
输出格式
Print the answers to the queries of the third type on separate lines.
输入输出样例
输入 #1
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
输出 #1
2 5 3
输入 #2
2 7 Add 1 7 Query 1 Add 2 4 Query 2 Color 1 1 1 Add 1 1 Query 2
输出 #2
7 7 8
说明/提示
The first sample test is explained below. Blue, red and green represent colors $1$ , $2$ and $3$ respectively.
