[Solution] Colorful Operations solution codeforces

Colorful Operations solution codeforces – You have an array 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an. Each element initially has value 00 and color 11. You are also given 𝑞q queries to perform:

  • Color 𝑙l 𝑟r 𝑐c: Change the color of elements 𝑎𝑙,𝑎𝑙+1,,𝑎𝑟al,al+1,⋯,ar to 𝑐c (1𝑙𝑟𝑛1≤l≤r≤n1𝑐𝑛1≤c≤n).
  • Add 𝑐c 𝑥x: Add 𝑥x to values of all elements 𝑎𝑖ai (1𝑖𝑛1≤i≤n) of color 𝑐c (1𝑐𝑛1≤c≤n109𝑥109−109≤x≤109).
  • Query 𝑖i: Print 𝑎𝑖ai (1𝑖𝑛1≤i≤n).

Colorful Operations solution codeforces

The first line of input contains two integers 𝑛n and 𝑞q (1𝑛,𝑞1061≤n,q≤106) — 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.

Output

Print the answers to the queries of the third type on separate lines.

Examples
input

Copy
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

Colorful Operations solution codeforces

2
5
3
input

Copy
2 7
Add 1 7
Query 1
Add 2 4
Query 2
Color 1 1 1
Add 1 1
Query 2
output

Copy
7
7
8

Colorful Operations solution codeforces

The first sample test is explained below. Blue, red and green represent colors 1122 and 33 respectively.

Colorful Operations solution codeforces

Leave a Comment