[Solution] Monoblock solution codeforces

Table of Contents

Monoblock solution codeforces

Monoblock solution codeforces – Stanley has decided to buy a new desktop PC made by the company “Monoblock”, and to solve captcha on their website, he needs to solve the following task.

The awesomeness of an array is the minimum number of blocks of consecutive identical numbers in which the array could be split. For example, the awesomeness of an array

  • [1,1,1][1,1,1] is 11;
  • [5,7][5,7] is 22, as it could be split into blocks [5][5] and [7][7];
  • [1,7,7,7,7,7,7,7,9,9,9,9,9,9,9,9,9][1,7,7,7,7,7,7,7,9,9,9,9,9,9,9,9,9] is 3, as it could be split into blocks [1][1][7,7,7,7,7,7,7][7,7,7,7,7,7,7], and [9,9,9,9,9,9,9,9,9][9,9,9,9,9,9,9,9,9].

[Solution] Monoblock solution codeforces

You are given an array 𝑎a of length 𝑛n. There are 𝑚m queries of two integers 𝑖i𝑥x. A query 𝑖i𝑥x means that from now on the 𝑖i-th element of the array 𝑎a is equal to 𝑥x.

After each query print the sum of awesomeness values among all subsegments of array 𝑎a. In other words, after each query you need to calculate

𝑙=1𝑛𝑟=𝑙𝑛𝑔(𝑙,𝑟),∑l=1n∑r=lng(l,r),

where 𝑔(𝑙,𝑟)g(l,r) is the awesomeness of the array 𝑏=[𝑎𝑙,𝑎𝑙+1,,𝑎𝑟]b=[al,al+1,…,ar].

Input

In the first line you are given with two integers 𝑛n and 𝑚m (1𝑛,𝑚1051≤n,m≤105).

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109) — the array 𝑎a.

In the next 𝑚m lines you are given the descriptions of queries. Each line contains two integers 𝑖i and 𝑥x (1𝑖𝑛1≤i≤n1𝑥1091≤x≤109).

[Solution] Monoblock solution codeforces

Print the answer to each query on a new line.

Example
input

Copy
5 5
1 2 3 4 5
3 2
4 2
3 1
2 1
2 2
output

Copy
29
23
35
25
35

[Solution] Monoblock solution codeforces

After the first query 𝑎a is equal to [1,2,2,4,5][1,2,2,4,5], and the answer is 2929 because we can split each of the subsegments the following way:

  1. [1;1][1;1][1][1], 1 block;
  2. [1;2][1;2][1]+[2][1]+[2], 2 blocks;
  3. [1;3][1;3][1]+[2,2][1]+[2,2], 2 blocks;
  4. [1;4][1;4][1]+[2,2]+[4][1]+[2,2]+[4], 3 blocks;
  5. [1;5][1;5][1]+[2,2]+[4]+[5][1]+[2,2]+[4]+[5], 4 blocks;
  6. [2;2][2;2][2][2], 1 block;
  7. [2;3][2;3][2,2][2,2], 1 block;
  8. [2;4][2;4][2,2]+[4][2,2]+[4], 2 blocks;
  9. [2;5][2;5][2,2]+[4]+[5][2,2]+[4]+[5], 3 blocks;
  10. [3;3][3;3][2][2], 1 block;
  11. [3;4][3;4][2]+[4][2]+[4], 2 blocks;
  12. [3;5][3;5][2]+[4]+[5][2]+[4]+[5], 3 blocks;
  13. [4;4][4;4][4][4], 1 block;
  14. [4;5][4;5][4]+[5][4]+[5], 2 blocks;
  15. [5;5][5;5][5][5], 1 block;

which is 1+2+2+3+4+1+1+2+3+1+2+3+1+2+1=291+2+2+3+4+1+1+2+3+1+2+3+1+2+1=29 in total.

For Solution

“Click Here”

Leave a Comment