Sequence Master solution codechef

 

Given is a sequence AA of length NN.

Define f(i,j)f(i,j) to be the number of distinct elements in Ai,Ai+1,…,AjAi,Ai+1,…,Aj.

You need to process QQ queries of the following two types:

• 1 x y1 x y — set Ax=yAx=y.
• 2 k2 k — print ∑i=1k∑j=ikf(i,j)∑i=1k∑j=ikf(i,j).

Input Format

• The first line of input contains two integers NN and QQ — the size of the array and the number of queries.
• The second line of input contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
• Then, QQ lines follow, describing queries in the format given in the statement.

Output Format

For each type 22 query, print the answer to it on a new line.

Constraints

• 1≤N,Q≤2⋅1051≤N,Q≤2⋅105
• 1≤Ai≤N1≤Ai≤N
• 1≤x,y≤N1≤x,y≤N
• 1≤k≤N1≤k≤N

Subtasks

• Subtask 1 (20 points): No type 11 queries
• Subtask 2 (80 points): Original constraints

Sample Input 1 

3 2
1 2 2
2 2
2 3

Sample Output 1 

4
8

Explanation

Test Case 11: The answer is f(1,1)+f(1,2)+f(2,2)=1+2+1=4f(1,1)+f(1,2)+f(2,2)=1+2+1=4.

Test Case 22: The answer is f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+2+1+1+1=8f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+2+1+1+1=8.

Sample Input 2 

5 5
1 2 3 4 5
2 5
1 1 2
2 3
2 4
2 5

Sample Output 2 

35
8
17
31

• For Solution

  Click Here!