Colorful Operations

题意翻译

你有一个长度为 $n$ 的数组。对于所有在 $[1,n]$ 内的整数 $i$，第 $i$ 个元素 $a_i$ 一开始的值为 $0$，颜色为 $1$。 你需要执行 $q$ 次操作，每次操作为如下三种之一： 1. $\texttt\colorbox{lightgrey}{Color l r c}$：将 $a_l,a_{l+1},\cdots,a_r$ 的颜色替换为 $c$。 2. $\texttt\colorbox{lightgrey}{Add c x}$：将数组中颜色为 $c$ 的所有元素的值加上 $x$。 3. $\texttt\colorbox{lightgrey}{Query i}$：输出 $a_i$ 的值。 数据范围： - $1\leqslant n,q\leqslant 10^6$。 - 对于操作 1，$1\leqslant l\leqslant r\leqslant n$，$1\leqslant c\leqslant n$。 - 对于操作 2，$1\leqslant c\leqslant n$，$-10^9\leqslant x\leqslant 10^9$。 - 对于操作 3，$1\leqslant i\leqslant n$。 Translated by Eason_AC

题目描述

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 $ ).

输入输出格式

输入格式

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.

输出格式

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. 

题意翻译

你有一个长度为 $n$ 的数组。对于所有在 $[1,n]$ 内的整数 $i$，第 $i$ 个元素 $a_i$ 一开始的值为 $0$，颜色为 $1$。 你需要执行 $q$ 次操作，每次操作为如下三种之一： 1. $\texttt\colorbox{lightgrey}{Color l r c}$：将 $a_l,a_{l+1},\cdots,a_r$ 的颜色替换为 $c$。 2. $\texttt\colorbox{lightgrey}{Add c x}$：将数组中颜色为 $c$ 的所有元素的值加上 $x$。 3. $\texttt\colorbox{lightgrey}{Query i}$：输出 $a_i$ 的值。 数据范围： - $1\leqslant n,q\leqslant 10^6$。 - 对于操作 1，$1\leqslant l\leqslant r\leqslant n$，$1\leqslant c\leqslant n$。 - 对于操作 2，$1\leqslant c\leqslant n$，$-10^9\leqslant x\leqslant 10^9$。 - 对于操作 3，$1\leqslant i\leqslant n$。 Translated by Eason_AC